2021/03/02 by Nastaran Haghparast, Haghparast, Nastaran, Morteza Hasanvand +3
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Topology and Set Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2103.02034
In 1967 Harary, Hedetniemi, and Prins showed that every graph G admits a\ncomplete t-coloring for every t with \χ(G) \≤ t \≤ \ψ(G), where\n\χ(G) denotes the chromatic number of G and \ψ(G) denotes the\nachromatic number of G which is the maximum number r for which G admits a\ncomplete r-coloring. Recently, Edwards and Rz c a .zewski (2020) showed\nthat this result fails for hypergraphs by proving that for every integer k\nwith k\≥ 9, there exists a k-uniform hypergraph H with a complete\n\χ(H)-coloring and a complete \ψ(H)-coloring, but no complete\nt-coloring for some t with \χ(H)< t<\ψ(H). They also asked whether\nthere would exist such an example for 3-uniform hypergraphs and posed another\nproblem to strengthen their result. In this paper, we generalize their result\nto all cases k with k\≥ 3 and settle their problems by giving several\nkinds of 3-uniform hypergraphs. In particular, we disprove a recent\nconjecture due to Matsumoto and the third author (2020) who suggested a special\nfamily of 3-uniform hypergraph to satisfy the desired interpolation property.\n