Equitable coloring of hypergraphs
Hanna Furmańczyk , Paweł Obszarski
AbstractA 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.
|Journal series||Discrete Applied Mathematics, ISSN 0166-218X, (N/A 70 pkt)|
|Publication size in sheets||0.50|
|Keywords in English||equitable coloring, hypergraph, linear hypertree, feasible sequence|
|Score||= 70.0, 26-02-2020, ArticleFromJournal|
|Publication indicators||= 0.000; : 2018 = 1.263; : 2018 = 0.983 (2) - 2018=1.029 (5)|
|Citation count*||1 (2020-07-06)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.