- Tytuł:
- Parity vertex colouring of graphs
- Autorzy:
-
Borowiecki, Piotr
Budajová, Kristína
Jendrol', Stanislav
Krajci, Stanislav - Powiązania:
- https://bibliotekanauki.pl/articles/743850.pdf
- Data publikacji:
- 2011
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
parity colouring
graph colouring
vertex ranking
ordered colouring
tree
hypercube
Fibonacci number - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2011, 31, 1; 183-195
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł