Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs

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
0
Scopus

Hanna Furmańczyk, Marek Kubale. (2018). Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs, 237, 116-122. https://doi.org/10.1016/j.dam.2017.12.002

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

wyświetlono 8 razy

Publikacje, które mogą cię zainteresować

Meta Tagi