Detour chromatic numbers

Marietjie Frick; Frank Bullock

Discussiones Mathematicae Graph Theory (2001)

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

Abstract

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

How to cite

top

Marietjie 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. [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. [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. [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. [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. [5] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman & Hall, London, 3rd Edition, 1996). 
  6. [6] J.E. Dunbar and M. Frick, Path kernels and partitions, JCMCC 31 (1999) 137-149. Zbl0941.05040
  7. [7] J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pₙ-free sets, submitted. Zbl1056.05085
  8. [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. [9] P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985). 

NotesEmbed ?

top

You must be logged in to post comments.