Colorings v.s. list colorings of uniform hypergraphs

2018/04/09 by Wang, Wei, Qian, Jianguo, Yan, Zhidan
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1804.02852

Abstract

Let r be an integer with r≥ 2 and G be a connected r-uniform hypergraph with m edges. By refining the broken cycle theorem for hypergraphs, we show that if k>(m-1)/(ln(1+√(2)))≈ 1.135 (m-1) then the k-list assignment of G admitting the fewest colorings is the constant list assignment. This extends the previous results of Donner, Thomassen and the current authors for graphs.

Related

• Comparing list-color functions of uniform hypergraphs with their chromatic polynomials
• Comparing list-color functions of uniform hypergraphs with their chromatic polynomials (III)
• Compare list-color functions of uniform hypergraphs with their chromatic polynomials (II)
• List colorings of k-partite k-graphs
• Improved bounds for coloring locally sparse hypergraphs