On Equitable List Arboricity of Graphs

NEW

Problem: Work with finite simple graphs. Let $P_n$ have ordered vertices $v_1,\dots,v_n$, and let $P_n^p$ join $v_i,v_j$ iff $0<|i-j|\le p$. A $k$-assignment $L$ gives each vertex exactly $k$ available colors. An equitable arborable $L$-coloring is a map $f$ with $f(v)\in L(v)$, no color used more than $\lceil |V(G)|/k\rceil$ times, and every color class inducing a forest. $G$ is equitably $k$-list arborable if this holds for every $k$-assignment.

Reconstructed conjecture: for $n,p\in\mathbb N$, $n\ge p+1$,

This is exactly the quoted Conjecture 1.9/9 from the supplied metadata.

Result: The conjecture is true. In fact, for every $n\ge1$, $P_n^p$ is equitably $k$-list arborable whenever $2k\ge p+1$.

Proof. Put $m=2k$, so $p\le m-1$. We prove the sufficiency by induction on $n$.

If $n\le k$, then for any $k$-assignment Hall’s theorem gives distinct colors for all vertices, since every nonempty union of lists has size at least $k\ge n$. If $k<n\le2k$, replace each color by two copies; Hall gives an assignment using each original color at most twice, since for every vertex set $X$,

Every color class has size at most $2=\lceil n/k\rceil$ and hence induces a forest.

Now assume $n>2k$. Let

By induction, $G-S\cong P_{n-2k}^p$ has an equitable arborable $L$-coloring $f$. Let

Thus every color is used by $f$ at most $q'$ times.

For each $v_i\in S$ and color $c\in L(v_i)$, let

Create two formal slots $c^0,c^1$ for every color $c$. Define a slot-list $M_i$ by including both $c^0,c^1$ if $t_i(c)=0$, including only $c^0$ if $t_i(c)=1$, and including neither if $t_i(c)\ge2$.

Let $r_i=|N_G(v_i)\setminus S|$. Since $p\le2k-1$, we have $r_i\le i-1$. Also,

Indeed, starting with $2k$ slots from $L(v_i)$, each outside neighbor colored by a color in $L(v_i)$ can delete at most one slot-count unit, and there are at most $r_i$ such neighbors.

By Hall’s theorem, the sets $M_1,\dots,M_{2k}$ have distinct representatives: for any $X\subseteq\{1,\dots,2k\}$, if $a=\min X$, then

Assign $v_i$ the original color of its chosen slot. Then each color is used on $S$ at most twice. Moreover, for any color $c$, at most one vertex of $S$ colored $c$ has an outside neighbor colored $c$, because all such “dangerous” uses require the single slot $c^0$.

Combining this coloring of $S$ with $f$, each color is used at most $q'+2=q$ times. For acyclicity, fix a color $c$. Its old color class in $G-S$ is a forest; its new part inside $S$ has size at most two, hence is a forest; and there is at most one edge between these two parts. Adding at most one connecting edge between forests cannot create a cycle. Thus every color class remains acyclic.

So $P_n^p$ is equitably $k$-list arborable whenever $2k\ge p+1$.

For necessity, assume $n\ge p+1$. The vertices $v_1,\dots,v_{p+1}$ form a clique $K_{p+1}$. If $2k<p+1$, give every vertex the same list of $k$ colors. Some color appears on at least three vertices of this clique, producing a monochromatic triangle, so no arborable coloring exists. Hence $k\ge\lceil(p+1)/2\rceil$ is necessary.

Therefore the stated “if and only if” holds.

Audit: The proof uses exactly the paper’s definition of equitable $k$-list arborability, allows arbitrary $k$-assignments, proves all $k\ge\lceil(p+1)/2\rceil$, and the lower bound uses only the required hypothesis $n\ge p+1$.

Citation: Conjecture and terminology: Hemanshu Kaul, Jeffrey A. Mudrock, Michael J. Pelsmajer, “On Equitable List Arboricity of Graphs,” arXiv:2008.08926, Conjecture 1.9. The resolution above is self-contained.