# 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

## Access Full Article

top## Abstract

top## How to cite

topPiotr 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] 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] 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] D. Dereniowski, Rank colouring of graphs, in: M. Kubale ed., Graph Colorings, Contemporary Mathematics 352 (American Mathematical Society, 2004) 79-93.
- [4] R. Diestel, Graph Theory (Springer-Verlag New York, Inc., 1997).
- [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] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
- [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] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (Morgan Kaufmann, San Mateo, CA, 1992). Zbl0743.68007
- [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] 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