Abstract:
We prove an analog of Borodin's Theorem on $d$-colorings for arboricity. A tree vertex coloring is a coloring of vertices of a graph such that the induced subgraph on any color is acyclic. A connected graph $G$ is an even Gallai tree, if each its block is either a simple cycle or a complete graph on odd number of vertcices. A list $L = \{L(v)\}_{v\in V(G)}$ is a $d/2$-list, if $|L(v)|\ge {d_G(v)/2}$ for any vertex $v$. It is proved that if a connected graph is not an even Gallai tree, then it has a tree coloring according to any $d/2$-list.
Key words and phrases:vertex arboricity, list arboricity, $d$-colorings.
Fulltext:
PDF file (264 kB)