Return to Answer

Greedy coloring works here to show $2p$-choosability, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i-1$ neighbors in $B$ and vice versa.

First color the edges in the bigraph between $A$ and $B$; observe that each such edge is adjacent (in $L(G)$) to at most $2p-1$ previously colored edges when it is processed, thus has a color available. (Alternatively, just use Galvin's theorem for this part; then these edges only need to have lists of size $p$.)

Then color the edges $a_ia_j$ within $A$, ordering the edges so that $i + j$ is non-increasing. Observe that an edge $a_ia_j$ with $i \leq j$ has, within the clique $A$, exactly $p+1-j$ previously-colored adjacent edges at its $a_i$-endpoint and $(p+1)-i-1 = p-i$ previously-colored adjacent edges at its $a_j$-endpoint, for a total of $2p+1-(i+j)$ previously-colored neighbor edges within $A$. Furthermore, $a_ia_j$ has exactly $(i-1) + (j-1) = i+j-2$ previously-colored adjacent edges going to $B$. Thus, each edge $a_ia_j$ within $A$ is adjacent to exactly $2p-1$ previously-colored edges when it is processed, and therefore has a color available. Coloring $B$ the same way finishes the proof.

Greedy coloring works here to show $2p$-choosability, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i-1$ neighbors in $B$ and vice versa.

First color the edges in the bigraph between $A$ and $B$; observe that each such edge is adjacent (in $L(G)$) to at most $2p-1$ previously colored edges when it is processed, thus has a color available. (Alternatively, just use Galvin's theorem for this part; then these edges only need to have lists of size $p$.)

Then color the edges $a_ia_j$ within $A$, ordering the edges so that $i + j$ is non-increasing. Observe that an edge $a_ia_j$ with $i \leq j$ has, within the clique $A$, exactly $p+1-j$ previously-colored adjacent edges at its $a_i$-endpoint and $(p+1)-i-1 = p-i$ previously-colored adjacent edges at its $a_j$-endpoint, for a total of $$2p+1-(i+j)$$ previously-colored adjacent edges within $A$. Furthermore, $a_ia_j$ has exactly $$(i-1) + (j-1) = i+j-2$$ previously-colored adjacent edges going to $B$. Thus, each edge $a_ia_j$ within $A$ is adjacent to exactly $2p-1$ previously-colored edges when it is processed, and therefore has a color available. Coloring $B$ the same way finishes the proof.

Greedy coloring works here to show $2p$-choosability, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i-1$ neighbors in $B$ and vice versa.

First color the edges in the bigraph between $A$ and $B$; observe that each such edge is adjacent (in $L(G)$) to at most $2p-1$ previously colored edges when it is processed, thus has a color available.

Then color the edges $a_ia_j$ within $A$, ordering the edges so that $i + j$ is non-increasing. Observe that an edge $a_ia_j$ with $i \leq j$ has, within the clique $A$, exactly $p+1-j$ previously-colored adjacent edges at its $a_i$-endpoint and $(p+1)-i-1 = p-i$ previously-colored adjacent edges at its $a_j$-endpoint, for a total of $2p+1-(i+j)$ previously-colored neighbors within $A$. Furthermore, $a_ia_j$ has exactly $(i-1) + (j-1) = i+j-2$ previously-colored adjacent edges going to $B$. Thus, each edge $a_ia_j$ within $A$ is adjacent to exactly $2p-1$ previously-colored edges when it is processed, and therefore has a color available. Coloring $B$ the same way finishes the proof.

Greedy coloring works here to show $2p$-choosability, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i-1$ neighbors in $B$ and vice versa.

First color the edges in the bigraph between $A$ and $B$; observe that each such edge is adjacent (in $L(G)$) to at most $2p-1$ previously colored edges when it is processed, thus has a color available. (Alternatively, just use Galvin's theorem for this part; then these edges only need to have lists of size $p$.)

Then color the edges $a_ia_j$ within $A$, ordering the edges so that $i + j$ is non-increasing. Observe that an edge $a_ia_j$ with $i \leq j$ has, within the clique $A$, exactly $p+1-j$ previously-colored adjacent edges at its $a_i$-endpoint and $(p+1)-i-1 = p-i$ previously-colored adjacent edges at its $a_j$-endpoint, for a total of $2p+1-(i+j)$ previously-colored neighbor edges within $A$. Furthermore, $a_ia_j$ has exactly $(i-1) + (j-1) = i+j-2$ previously-colored adjacent edges going to $B$. Thus, each edge $a_ia_j$ within $A$ is adjacent to exactly $2p-1$ previously-colored edges when it is processed, and therefore has a color available. Coloring $B$ the same way finishes the proof.

Greedy coloring works here, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i$ neighbors in $B$ and vice versa.

First color the edges in the bigraph between $A$ and $B$; observe that each such edge is adjacent (in $L(G)$) to at most $2p-1$ previously colored edges when it is processed, thus has a color available.

Then color the edges $a_ia_j$ within $A$, ordering the edges so that $a_i + a_j$ is non-increasing. Observe that an edge $a_ia_j$ with $i \leq j$ has exactly $p+1-j$ previously-colored adjacent edges at its $a_i$-endpoint and $(p+1)-i-1 = p-i$ previously-colored adjacent edges at its $a_j$-endpoint, for a total of $2p+1-(i+j)$ previously-colored neighbors within $A$. OOPS THIS IS NOT QUITE GOOD ENOUGH, WE ARE OFF BY ONE

Greedy coloring works here to show $2p$-choosability, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i-1$ neighbors in $B$ and vice versa.

First color the edges in the bigraph between $A$ and $B$; observe that each such edge is adjacent (in $L(G)$) to at most $2p-1$ previously colored edges when it is processed, thus has a color available.

Then color the edges $a_ia_j$ within $A$, ordering the edges so that $i + j$ is non-increasing. Observe that an edge $a_ia_j$ with $i \leq j$ has, within the clique $A$, exactly $p+1-j$ previously-colored adjacent edges at its $a_i$-endpoint and $(p+1)-i-1 = p-i$ previously-colored adjacent edges at its $a_j$-endpoint, for a total of $2p+1-(i+j)$ previously-colored neighbors within $A$. Furthermore, $a_ia_j$ has exactly $(i-1) + (j-1) = i+j-2$ previously-colored adjacent edges going to $B$. Thus, each edge $a_ia_j$ within $A$ is adjacent to exactly $2p-1$ previously-colored edges when it is processed, and therefore has a color available. Coloring $B$ the same way finishes the proof.