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

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.

10 pages, no figures; updated according to referee suggestions