Comparing list-color functions of uniform hypergraphs with their chromatic polynomials (III)

2022/12/05 by Fengming Dong, Dong, Fengming, Meiqiao Zhang +1
Computer Science · Engineering · #05C15 #05C30 #05C31 #Combinatorics (math.CO) #Computational Drug Discovery Methods #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2212.02045

openalex publication_date 2022/12/05 · openalex created_date 2022/12/18 · openalex updated_date 2026/07/28

Abstract

For a hypergraph \cal H, let P(\cal H,k) and P_l(\cal H,k) be its chromatic polynomial and list-color function respectively, and let τ'(\cal H) be the least non-negative integer q such that P(\cal H,k)=P_l(\cal H,k) holds for all integers k≥ q. In this article, we show that for any r-uniform hypergraph \cal H of order n and size m and any k-assignment L of \cal H, where r≥ 3, P(\cal H,L)-P(\cal H,k)≥ min \0.02k, k-(m-1)\ k^n-r-1∑_e∈ E(\cal H) ( k- |\bigcap_{v∈ e}L(v) | ) holds for k≥ m-1≥ 4. It follows that τ'(\cal H)≤ m-1, improving the current best result on τ'(\cal H).

Related

• Comparing list-color functions of uniform hypergraphs with their chromatic polynomials
• Compare list-color functions of uniform hypergraphs with their chromatic polynomials (II)
• Colorings v.s. list colorings of uniform hypergraphs
• DP color functions of hypergraphs
• On the List Color Function Threshold