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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.