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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.26493/1855-3974.1083.54f | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Homogenous coloring,mixed hypergraph,bi-hypergraph,NMNR-coloring | Complete coloring,Edge coloring,Discrete mathematics,Topology,Combinatorics,Fractional coloring,List coloring,Bipartite graph,Brooks' theorem,Greedy coloring,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
12 | 2 | 1855-3966 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mária Janicová | 1 | 0 | 0.34 |
Tomáš Madaras | 2 | 112 | 11.15 |
Roman Soták | 3 | 128 | 24.06 |
Borut Luzar | 4 | 42 | 10.86 |