Lucky k-polynomials of null and complete split graphs

NEW

Problem: Reconstructed statement: for finite simple graphs $G,H$, $G+H$ denotes the join. Kok’s $L_G(\lambda,k)$ counts exact proper $k$-colorings using colors from a $\lambda$-set that maximize the chromatic-completion number. Equivalently,

where $m_G(k)$ is the number of unordered independent $k$-partitions attaining the maximum, and $(\lambda)_k=\lambda(\lambda-1)\cdots(\lambda-k+1)$. The displayed problem claims

If interpreted merely as “compute this displayed maximum,” a linear scan over $\ell$ suffices. Interpreted as a formula for the Lucky polynomial of the join, it is false.

Result: Take $G=H=N_2$, the null graph on two vertices, and $k=3$. Then $G+H=K_{2,2}$.

For $N_2$,

Thus the proposed formula gives

But in $K_{2,2}$, an exact proper $3$-partition must split exactly one of the two independent sides into two singleton color classes and keep the other side as one class. There are two such unordered partitions, and each permits exactly one completion edge, which is maximal. Hence

contradicting the displayed formula.

The natural repair is to maximize completion numbers, not products of Lucky-polynomial coefficients. For a graph $X$, let $\zeta_X(r)$ be the maximum number of addable completion edges over exact proper $r$-partitions, and let $m_X(r)$ count the partitions attaining it. Then

with valid range $\chi(G)\le \ell\le k-\chi(H)$, and

Proof: every color class of a join lies wholly in $G$ or wholly in $H$; all $G$-$H$ edges are already present, so completion edges split exactly into completion edges inside $G$ and inside $H$. Therefore optimal join colorings are precisely pairs of component-optimal colorings for those $\ell$ attaining the maximum sum above.

Citation: Definitions and problem source: Johan Kok, “Lucky $k$-polynomials of null and complete split graphs,” Open Journal of Discrete Applied Mathematics 5(1), 52–58, 2022. The counterexample and repaired formula above are elementary and not taken from a prior source.