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

  • 1

    CrossRef

  • 0

    Web of Science

  • 2

    Scopus

Autorzy (2)

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

Publikacje, które mogą cię zainteresować

Meta Tagi