Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Parity vertex colouring of graphs

100%

Borowiecki P., Budajová K., Jendrol' S., Krajci S.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 1

183-195

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Borowiecki P.

1 Budajová K.

1 Jendrol' S.

1 Krajci S.

1 2011

Wyniki wyszukiwania

Parity vertex colouring of graphs