DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 283-291
DOI: 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