Detour chromatic numbers
Marietjie Frick ; Frank Bullock
Discussiones Mathematicae Graph Theory, Tome 21 (2001), p. 283-291 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270269 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1150,
     author = {Marietjie Frick and Frank Bullock},
     title = {Detour chromatic numbers},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {283-291},
     zbl = {1002.05021},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1150}
}

Marietjie Frick; Frank Bullock. Detour chromatic numbers. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 283-291. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1150/

[000] [1] 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. | Zbl 0902.05026

[001] [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. | Zbl 0912.05048

[002] [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. | Zbl 0906.05059

[003] [4] G. Chartrand, D.P. Geller and S. Hedetniemi, A generalization of the chromatic number, Proc. Cambridge Phil. Soc. 64 (1968) 265-271. | Zbl 0173.26204

[004] [5] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman & Hall, London, 3rd Edition, 1996).

[005] [6] J.E. Dunbar and M. Frick, Path kernels and partitions, JCMCC 31 (1999) 137-149. | Zbl 0941.05040

[006] [7] J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pₙ-free sets, submitted. | Zbl 1056.05085

[007] [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. | Zbl 0871.05040

[008] [9] P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985).