Triangle-free graphs of tree-width t are ceil((t + 3)/2)-colorable

Zden\v{e}k Dvo\v{r}\'ak , Ken-ichi Kawarabayashi

Authors on Pith no claims yet

classification 🧮 math.CO

keywords graphstree-widthceilcoloringtriangle-freeargumentboundchromatic

read the original abstract

We prove that every triangle-free graph of tree-width t has chromatic number at most ceil((t + 3)/2), and demonstrate that this bound is tight. The argument also establishes a connection between coloring graphs of tree-width t and on-line coloring of graphs of path-width t.

This paper has not been read by Pith yet.

Triangle-free graphs of tree-width t are ceil((t + 3)/2)-colorable

discussion (0)