Parity vertex colouring of graphs

Piotr Borowiecki; Kristína Budajová; Stanislav Jendrol'; Stanislav Krajci

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 1, page 183-195
  • ISSN: 2083-5892

Abstract

top
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.

How to cite

top

Piotr Borowiecki, et al. "Parity vertex colouring of graphs." Discussiones Mathematicae Graph Theory 31.1 (2011): 183-195. <http://eudml.org/doc/271077>.

@article{PiotrBorowiecki2011,
abstract = {A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.},
author = {Piotr Borowiecki, Kristína Budajová, Stanislav Jendrol', Stanislav Krajci},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {parity colouring; graph colouring; vertex ranking; ordered colouring; tree; hypercube; Fibonacci number},
language = {eng},
number = {1},
pages = {183-195},
title = {Parity vertex colouring of graphs},
url = {http://eudml.org/doc/271077},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Piotr Borowiecki
AU - Kristína Budajová
AU - Stanislav Jendrol'
AU - Stanislav Krajci
TI - Parity vertex colouring of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 1
SP - 183
EP - 195
AB - A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T), then ⌈log₂(2+diam(T))⌉ ≤ χₚ(T) ≤ 1+rad(T). Both bounds are tight. The second thread of this paper is devoted to relationships between parity vertex colourings and vertex rankings, i.e. a proper vertex colourings with the property that each path between two vertices of the same colour q contains a vertex of colour greater than q. New results on graphs critical for vertex rankings are also presented.
LA - eng
KW - parity colouring; graph colouring; vertex ranking; ordered colouring; tree; hypercube; Fibonacci number
UR - http://eudml.org/doc/271077
ER -

References

top
  1. [1] H.L. Bodlaender, J.S. Degoun, K. Jansen, T. Kloks, D. Kratsch, H. Müller and Zs. Tuza, Rankings of graphs, SIAM J. Discrete Math. 11 (1998) 168-181, doi: 10.1137/S0895480195282550. 
  2. [2] D.P. Bunde, K. Milans, D.B. West and H. Wu, Parity and strong parity edge-colorings of graphs, Congr. Numer. 187 (2007) 193-213. Zbl1135.05020
  3. [3] D. Dereniowski, Rank colouring of graphs, in: M. Kubale ed., Graph Colorings, Contemporary Mathematics 352 (American Mathematical Society, 2004) 79-93. 
  4. [4] R. Diestel, Graph Theory (Springer-Verlag New York, Inc., 1997). 
  5. [5] G. Even, Z. Lotker, D. Ron and S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, SIAM Journal on Computing 33 (2003) 94-136, doi: 10.1137/S0097539702431840. Zbl1069.68120
  6. [6] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
  7. [7] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q. 
  8. [8] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (Morgan Kaufmann, San Mateo, CA, 1992). Zbl0743.68007
  9. [9] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl. 11 (1990) 134-172, doi: 10.1137/0611010. Zbl0697.65013
  10. [10] A. Sen, H. Deng and S. Guha, On a graph partition problem with application to VLSI layout, Inform. Process. Lett. 43 (1992) 87-94, doi: 10.1016/0020-0190(92)90017-P. Zbl0764.68132

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.