Wyszukiwarka
Abstrakt
In this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
Autorzy (2)
-
Hanna Furmańczyk
- Instytut Informatyki UG .
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Tytuł wydania:
- Bordeaux Graph Workshop strony 138 - 140
- Język:
- angielski
- Rok wydania:
- 2016
- Opis bibliograficzny:
- Kubale M., Furmańczyk H.: Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs// Bordeaux Graph Workshop/ Bordeaux: Eiseirb-Matmeca & LaBRI, 2016, s.138-140
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 124 razy