Download PDF - Detour chromatic numbers
ArticleOriginal scientific text
Title
Detour chromatic numbers
Authors 1, 1
Affiliations
- University of South Africa, P.O. Box 392, Unisa, 0003, South Africa
Abstract
The nth detour chromatic number, χₙ(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 χₙ(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
Bibliography
- M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanisin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
- 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.
- 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.
- G. Chartrand, D.P. Geller and S. Hedetniemi, A generalization of the chromatic number, Proc. Cambridge Phil. Soc. 64 (1968) 265-271.
- G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman & Hall, London, 3rd Edition, 1996).
- J.E. Dunbar and M. Frick, Path kernels and partitions, JCMCC 31 (1999) 137-149.
- J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pₙ-free sets, submitted.
- 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.
- P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985).
Pages:
283-291
Main language of publication
English
Received
2001-02-19
Accepted
2001-10-08
Published
2001
DOI: 10.7151/dmgt.1150
Exact and natural sciences