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

Fengming Dong; Meiqiao Zhang

paper

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

arXiv:2212.02045

Abstract

For a hypergraph $H$ , let $P (H, k)$ and $P_{l} (H, k)$ be its chromatic polynomial and list-color function respectively, and let $I ¨ ^{'} (H)$ be the least non-negative integer $q$ such that $P (H, k) = P_{l} (H, k)$ holds for all integers $k \geq q$ . In this article, we show that for any $r$ -uniform hypergraph $H$ of order $n$ and size $m$ and any $k$ -assignment $L$ of $H$ , where $r \geq 3$ , $P (H, L) - P (H, k) \geq min {0.02 k, k - (m - 1)} k^{n - r - 1} \sum_{e \in E (H)} (k - ⋂_{v \in e} L (v))$ holds for $k \geq m - 1 \geq 4$ . It follows that $I ¨ ^{'} (H) \leq m - 1$ , improving the current best result on $I ¨ ^{'} (H)$ .

This article is a sister paper of "Compare list-color functions of uniform hypergraphs with their chromatic polynomials (I)" at arXiv:2305.02497. The later is now completed in a new approach, and it covers the main result in the former