From NMNR-coloring of hypergraphs to homogenous coloring of graphs
Abstract
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.
Keywords
DOI: https://doi.org/10.26493/1855-3974.1083.54f
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