Equitable coloring of hypergraphs

Hanna Furmańczyk; Paweł Obszarski

doi:10.1016/j.dam.2019.01.016

Equitable coloring of hypergraphs

Abstract

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.

Citations

1

CrossRef
0

Web of Science
2

Scopus

Authors (2)

Hanna Furmańczyk
Paweł Obszarski dr

Cite as

Full text

download paper

downloaded 28 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2019.01.016
License: Copyright (2019 Elsevier B.V)

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach
Published in:: DISCRETE APPLIED MATHEMATICS no. 261, pages 186 - 192,
ISSN: 0166-218X
Language:: English
Publication year:: 2019
Bibliographic description:: Furmańczyk H., Obszarski P.: Equitable coloring of hypergraphs// DISCRETE APPLIED MATHEMATICS -Vol. 261, (2019), s.186-192
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2019.01.016
Verified by:: Gdańsk University of Technology