# Detour chromatic numbers

Marietjie Frick; Frank Bullock

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 2, page 283-291
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMarietjie Frick, and Frank Bullock. "Detour chromatic numbers." Discussiones Mathematicae Graph Theory 21.2 (2001): 283-291. <http://eudml.org/doc/270269>.

@article{MarietjieFrick2001,

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.},

author = {Marietjie Frick, Frank Bullock},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {detour; generalised chromatic number; longest path; vertex partition; girth; circumference; nearly bipartite; generalized colouring; path partition conjecture},

language = {eng},

number = {2},

pages = {283-291},

title = {Detour chromatic numbers},

url = {http://eudml.org/doc/270269},

volume = {21},

year = {2001},

}

TY - JOUR

AU - Marietjie Frick

AU - Frank Bullock

TI - Detour chromatic numbers

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 2

SP - 283

EP - 291

AB - 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.

LA - eng

KW - detour; generalised chromatic number; longest path; vertex partition; girth; circumference; nearly bipartite; generalized colouring; path partition conjecture

UR - http://eudml.org/doc/270269

ER -

## References

top- [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. Zbl0902.05026
- [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. Zbl0912.05048
- [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. Zbl0906.05059
- [4] G. Chartrand, D.P. Geller and S. Hedetniemi, A generalization of the chromatic number, Proc. Cambridge Phil. Soc. 64 (1968) 265-271. Zbl0173.26204
- [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. Zbl0941.05040
- [7] J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pₙ-free sets, submitted. Zbl1056.05085
- [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. Zbl0871.05040
- [9] P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985).

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.