Wyszukiwarka
Abstrakt
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 Xp(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 X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(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 ceil(log2(2+diam(T))) <= Xp(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.
Cytowania
-
3
CrossRef
-
0
Web of Science
-
7
Scopus
Autorzy (4)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.1537
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
Discussiones Mathematicae Graph Theory
nr 31,
strony 183 - 195,
ISSN: 1234-3099 - Język:
- angielski
- Rok wydania:
- 2011
- Opis bibliograficzny:
- Borowiecki P., Budajova K., Jendrol S., Krajci S.: Parity vertex colouring of graphs// Discussiones Mathematicae Graph Theory. -Vol. 31., iss. Iss 1 (2011), s.183-195
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.1537
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 77 razy
Publikacje, które mogą cię zainteresować
Bounds on the vertex-edge domination number of a tree
- B. Krishnakumari,
- Y. B. Venkatakrishnan,
- M. Krzywkowski
On extremal sizes of locally k-tree graphs
- M. Borowiecki,
- P. Borowiecki,
- E. Sidorowicz
- + 1 autorów