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.

Keywords

• Triangle-free
• graphs
• tree-width
• coloring