Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs

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)

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

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 19 razy

Publikacje, które mogą cię zainteresować

Meta Tagi