Discussiones Mathematicae Graph Theory 31(2) (2011) 345-356
doi: 10.7151/dmgt.1550

[BIBTex] [PDF] [PS]

Generalized Circular Colouring of Graphs

Peter Mihók

Department of Applied Mathematics
Faculty of Economics, Technical University Košice
B. Nemcovej 32, 040 01 Košice
Mathematical Institute, Slovak Academy of Science
Gresákova 6, 040 01 Košice, Slovak Republic

Janka Oravcová

Department of Applied Mathematics
Faculty of Economics, Technical University Košice
B. Nemcovej 32, 040 01 Košice, Slovak Republic

Roman Soták

Institute of Mathematics
Faculty of Science, P.J. Safárik University
Jesenná 5, 041 54 Košice, Slovak Republic

Abstract

Let P be a graph property and r,s ∈ N, r ≥ s. A strong circular (P,r,s)-colouring of a graph G is an assignment f:V(G)→ {0,1,...,r−1}, such that the edges uv ∈ E(G) satisfying |f(u)−f(v)| < s or |f(u)−f(v)| > r−s, induce a subgraph of G with the propery P. In this paper we present some basic results on strong circular (P,r,s)-colourings. We introduce the strong circular P-chromatic number of a graph and we determine the strong circular P-chromatic number of complete graphs for additive and hereditary graph properties.

Keywords: graph property, P-colouring, circular colouring, strong circular P-chromatic number

2010 Mathematics Subject Classification: 05C15, 05C75.

References

[1]J.A. Bondy and P. Hell, A Note on the Star Chromatic Number, J. Graph Theory 14 (1990) 479--482, doi: 10.1002/jgt.3190140412 .
[2]O. Borodin, On acyclic colouring of planar graphs, Discrete Math. 25 (1979) 211--236, doi: 10.1016/0012-365X(79)90077-3.
[3]M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, editor, Advances in Graph Theory (Vishwa International Publishers, 1991) 42--69.
[4]M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5--50, doi: 10.7151/dmgt.1037.
[5]W. Klostermeyer, Defective circular coloring, Austr. J. Combinatorics 26 (2002) 21--32.
[6]P. Mihók, On the lattice of additive hereditary properties of object systems, Tatra Mt. Math. Publ. 30 (2005) 155--161.
[7]P. Mihók, Zs. Tuza and M. Voigt, Fractional P-colourings and P-choice ratio, Tatra Mt. Math. Publ. 18 (1999) 69--77.

Received 22 January 2010
Revised 8 February 2011
Accepted 8 February 2011