Download PDF - Generalized circular colouring of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Generalized circular colouring of graphs

Authors 1, 2, 1, 3

Affiliations

  1. Department of Applied Mathematics Faculty of Economics, Technical University Košice, B. Nĕmcovej 32, 040 01 Košice, Slovak Republic
  2. Mathematical Institute, Slovak Academy of Science, Grešákova 6, 040 01 Košice, Slovak Republic
  3. Institute of Mathematics Faculty of Science, P.J. Šafá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

ENG
graph property, P-colouring, circular colouring, strong circular P-chromatic number

Bibliography

  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.
  8. A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551-559.
Discussiones Mathematicae Graph Theory
2011/31/2
Export to PBN, Opens in new tab
Pages:
345-356
Main language of publication
English
Received
2010-01-22
Accepted
2011-02-08
Published
2011

DOI: 10.7151/dmgt.1550

Exact and natural sciences