# List coloring as a homomorphism

A proper coloring of the vertices of a graph $$G$$ is seen as a homomorphism from the graph vertices to the complete graph on the number of vertices equal to the chromatic number of the graph. Similarly, the fractional coloring or $$a:b$$-coloring of vertices is seen as a homomorphism from the graph vertices to a Kneser graph $$K(a,b)$$ that is a graph whose vertices are $$b$$ subsets of an $$a$$-set with two vertices adjacent iff they are disjoint.

I wish to ask if there is a similar homomorphism characterization of the list coloring. I think this is somewhat related to the recent area of DP-coloring or correspondence coloring as in the paper. Any hints in this regard. Thanks beforehand.

If I googled 'list coloring' correctly, it is the following: For a graph $$G$$ we have at every vertex a given subset of colors. A lsit coloring chooses at every vertex one color from that list so that two adjacent vertices always have a different color.

From these lists we can form a new graph $$G'$$ with vertices pairs $$(v,c)$$ where $$v$$ is a vertex of $$G$$ and $$c$$ is a viable color of $$v$$. Two vertices $$(v,c),(v',c')$$ are adjacent, if $$v$$ and $$v'$$ are adjacent and $$c\neq c'$$.

We then have two canonical maps $$G'\to G$$ and $$G'\to C_n$$, where $$C_n$$ is the complete graph with $$n$$ vertices (given by the $$n$$ colors).

In this language a list coloring is a section of the map $$G'\to G$$.

• For example if all colors are allowed everywhere, then $G'=G\times C_n$ and hence a section $G\times C_n\rightarrow G$ is just a map $G\rightarrow C_n$. Apr 4 at 13:40
• In the OP's question, a homomorphism FROM the graph to either the complete graph (for colourings) or the Kneser graph (for fractional colourings) determines a valid colouring (or fractional colouring). So the "graph-to-be-coloured" is the domain of the homomorphism and the set of colours (encoded in some fashion) is the codomain. But here you are talking about a homomorphism TO the graph, and I can't see how this actually determines a list-colouring. Apr 5 at 5:28
• A section of $p:G'→G$ is a map $s:G→G′$ such that $p\circ s$ is the identity. So it is still a map from G to somewhere. The coloring of g is given by picking the second coordinate of s(g). Apr 5 at 9:33
• I am sorry if I am being dense here, but if I am correct, for each vertex $v \in G$ there is a set $(v,c_1)$, $(v,c_2)$, etc. of vertices of $G'$ with one vertex for each colour in the list for $v$, call this set a fibre. Then the map $G'\rightarrow G$ is just the projection onto the first coordinate. A section is then a choice of one vertex from each fibre. But how does this encode the colouring restriction? It seems like we can't take any section, but need the section ($s$ in your notation) to actually be a homomorphism? Apr 6 at 1:37
• Say we have two adjacent vertices $g,g'$ and $s(g)=(g,v)$ and $s(g')=(g',v')$, Since $s$ is a morphism in the category of graphs, we have that $g,g'$ are connected and $v,v'\in C_n$ are connected, i.e. $v,v'$ are different. Apr 6 at 9:32