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, (A 25 pkt)|
|Publication size in sheets||0.5|
|Keywords in English||equitable coloring, hypergraph, linear hypertree, feasible sequence|
|Score||= 25.0, 24-07-2019, ArticleFromJournal|
|Publication indicators||: 2016 = 1.17; : 2017 = 0.932 (2) - 2017=1.008 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.