Wyszukiwarka
Abstrakt
We consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
3
Scopus
Autorzy (2)
-
Hanna Furmańczyk
- Uniwersytet Gdański Instytut Informatyki
Cytuj jako
Pełna treść
pobierz publikację
pobrano 13 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2017.12.002
- Licencja
- Copyright (2017 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 237,
strony 116 - 122,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2018
- Opis bibliograficzny:
- Furmańczyk H., Kubale M.: Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 237, (2018), s.116-122
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2017.12.002
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 136 razy