Аннотация
The chromatic polynomial of a graph $G$, denoted $P(G,m)$, is equal to the
number of proper $m$-colorings of $G$. The list color function of graph $G$,
denoted $P_\ell(G,m)$, is a list analogue of the chromatic polynomial that
has been studied since the early 1990s, primarily through comparisons with the
corresponding chromatic polynomial. It is known that for any graph $G$ there is
a $k N$ such that $P_\ell(G,m) = P(G,m)$ whenever $m k$. The
list color function threshold of $G$, denoted $\tau(G)$, is the smallest $k
\chi(G)$ such that $P_\ell(G,m) = P(G,m)$ whenever $m k$. In 2009,
Thomassen asked whether there is a universal constant $\alpha$ such that for
any graph $G$, $\tau(G) \chi_\ell(G) + \alpha$, where $\chi_\ell(G)$
is the list chromatic number of $G$. We show that the answer to this question
is no by proving that there exists a constant $C$ such that $\tau(K_2,l) -
\chi_\ell(K_2,l) Cl$ for $l 16$.
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)