PDF
Discussiones
Mathematicae Graph Theory 21(1) (2001) 283-291
DOI: https://doi.org/10.7151/dmgt.1150
DETOUR CHROMATIC NUMBERS
Marietjie Frick and Frank Bullock
University of South Africa
P.O. Box 392, Unisa, 0003
South Africa
e-mail: frickm@unisa.ac.za
e-mail: bullofes@unisa.ac.za
Abstract
The nth detour chromatic number, χn(G) of a graph G is the minimum number of colours required to colour the vertices of G such that no path with more than n vertices is monocoloured. The number of vertices in a longest path of G is denoted by τ( G). We conjecture that χn(G) ≤ ⎡[(τ(G))/n]⎤ for every graph G and every n ≥ 1 and we prove results that support the conjecture. We also present some sufficient conditions for a graph to have nth chromatic number at most 2.Keywords: detour, generalised chromatic number, longest path, vertex partition, girth, circumference, nearly bipartite.
2000 Mathematics Subject Classification: 05C15, 05C38.
References
| [1] | M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semani~sin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. |
| [2] | I. Broere, M. Dorfling, J. E. Dunbar and M. Frick, A Pathological Partition Problem, Discuss. Math. Graph Theory 18 (1998) 113-125, doi: 10.7151/dmgt.1068. |
| [3] | I. Broere, P. Hajnal and P. Mihók, Partition problems and kernels of graphs, Discuss. Math. Graph Theory 17 (1997) 311-313, doi: 10.7151/dmgt.1058. |
| [4] | G. Chartrand, D.P. Geller and S. Hedetniemi, A generalization of the chromatic number, Proc. Cambridge Phil. Soc. 64 (1968) 265-271. |
| [5] | G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman & Hall, London, 3rd Edition, 1996). |
| [6] | J.E. Dunbar and M. Frick, Path kernels and partitions, JCMCC 31 (1999) 137-149. |
| [7] | J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pn-free sets, submitted. |
| [8] | E. Györi, A.V. Kostochka and T. Łuczak, Graphs without short odd cycles are nearly bipartite, Discrete Math. 163 (1997) 279-284, doi: 10.1016/0012-365X(95)00321-M. |
| [9] | P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985). |
Received 19 February 2001
Revised 8 October 2001
Close