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

Abstract: Let

c a l H

be any

r

-uniform hypergraph with

m

edges, where

r g e 3

,

P (c a l H, k)

be the chromatic polynomial of

c a l H

,

P (c a l H, L)

be the number of

L

-colorings of

c a l H

for any

k

-assignment

L

and

P_{l} (c a l H, k)

be the minimum value of

P (c a l H, L)

's among all

k

-assignments

L

. For any edge

e

in

c a l H

, let

E_{r - 1} (e)

denote the set of edges

e^{'}

in

c a l H

with

| e c a p e^{'} | = r - 1

, and let

g a m m a (c a l H) = m a x_{e i n E (c a l H)} | E_{r - 1} (e) |

. In this article, we show that

P_{l} (c a l H, k) = P (c a l H, k)

holds for all integers

k g e m i n m - 1, 0.6 (m - 1) + 0.5 g a m m a (c a l H)

. Our result improves the latest known result that

P_{l} (c a l H, k) = P (c a l H, k)

holds for all integers

k g e 1.1346 (m - 1)

.

This page was built for publication: Comparing list-color functions of uniform hypergraphs with their chromatic polynomials (III)