Equitable coloring of hypergraphs

Hanna Furmańczyk; Paweł Obszarski

doi:10.1016/j.dam.2019.01.016

Equitable coloring of hypergraphs

Abstrakt

A hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to equitably k-color linear hypertrees, where k≥2 is fixed.

Cytowania

1

CrossRef
0

Web of Science
2

Scopus

Autorzy (2)

Hanna Furmańczyk
Paweł Obszarski dr

Cytuj jako

Pełna treść

pobierz publikację

pobrano 28 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2019.01.016
Licencja: Copyright (2019 Elsevier B.V)

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuły w czasopismach
Opublikowano w:: DISCRETE APPLIED MATHEMATICS nr 261, strony 186 - 192,
ISSN: 0166-218X
Język:: angielski
Rok wydania:: 2019
Opis bibliograficzny:: Furmańczyk H., Obszarski P.: Equitable coloring of hypergraphs// DISCRETE APPLIED MATHEMATICS -Vol. 261, (2019), s.186-192
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2019.01.016
Weryfikacja:: Politechnika Gdańska