From NMNR-coloring of hypergraphs to homogenous coloring of graphs

Mária Janicová, Tomáš Madaras, Roman Soták, Borut Lužar


An NMNR-coloring of a hypergraph is a coloring of vertices such that in every hyperedge at least two vertices are colored with distinct colors, and at least two vertices are colored with the same color. We prove that every 3-uniform 3-regular hypergraph admits an NMNR-coloring with at most 3 colors. As a corollary, we confirm the conjecture that every bipartite cubic graph admits a 2-homogenous coloring, where a k-homogenous coloring of a graph G is a proper coloring of vertices such that the number of colors in the neigborhood of any vertex equals k. We also introduce several other results and propose some additional problems.


Homogenous coloring, mixed hypergraph, bi-hypergraph, NMNR-coloring

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications