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.


1 Answer 1


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$.

  • $\begingroup$ 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$. $\endgroup$ Apr 4 at 13:40
  • $\begingroup$ 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. $\endgroup$ Apr 5 at 5:28
  • 1
    $\begingroup$ 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). $\endgroup$ Apr 5 at 9:33
  • $\begingroup$ 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? $\endgroup$ Apr 6 at 1:37
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 6 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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