Discussiones Mathematicae Graph Theory 31(2) (2011)
345-356
DOI: https://doi.org/10.7151/dmgt.1550
Generalized Circular Colouring of Graphs
| Peter Mihók
Department of Applied Mathematics | Janka Oravcová
Department of Applied Mathematics | Roman Soták
Institute of Mathematics |
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
Close