Equitable coloring of hypergraphs

Hanna Furmańczyk , Paweł Obszarski


A hypergraph is equitably k-colorable if its vertices can be partitioned into k sets/color classes in such a way that monochromatic edges are avoided and the number of vertices in 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.
Author Hanna Furmańczyk (FMPI / II)
Hanna Furmańczyk,,
- Institute of Informatics
, Paweł Obszarski
Paweł Obszarski,,
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X, (N/A 70 pkt)
Issue year2019
Publication size in sheets0.5
Keywords in Englishequitable coloring, hypergraph, linear hypertree, feasible sequence
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
URL https://doi.org/10.1016/j.dam.2019.01.016
Languageen angielski
Score (nominal)70
ScoreMinisterial score = 70.0, 30-09-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.17; WoS Impact Factor: 2017 = 0.932 (2) - 2017=1.008 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.