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.50
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
Score sourcejournalList
ScoreMinisterial score = 70.0, 26-02-2020, ArticleFromJournal
Publication indicators WoS Citations = 0.000; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.263; WoS Impact Factor: 2018 = 0.983 (2) - 2018=1.029 (5)
Citation count*1 (2020-07-06)
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.
Are you sure?