1
$\begingroup$

Consider a non-regular bipartite graph $G$ . We consider list edge coloring the edges of the graph by giving lists of cardinality $max(deg(v_i),deg(v_j))+2$ for each edge $e=v_iv_j$ where $deg(v_i)$ denotes the degree of the vertex $v_i$.

Then, is the graph $G$ properly colorable. If so, would the maximum cardinality of the lists be $\Delta+2$ where $\Delta$ be the maximum degree of $G$? Is this version of list coloring of $G$ similar to online list coloring? I also see it is exactly somewhat similar to the concept of $f-$ chhosabality of the graphs, where $f$ is the choice function for edge. Thanks beforehand.

$\endgroup$

1 Answer 1

2
$\begingroup$

This problem can indeed be solved using online list coloring. The stronger result that you can use lists of size $\max(\deg(v_i),\deg(v_j))$ is proven as Theorem 3.3 in this paper of Uwe Schauz.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.