| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 5777360 | European Journal of Combinatorics | 2017 | 6 Pages |
Abstract
We prove that every triangle-free graph of tree-width t has chromatic number at most â(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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
ZdenÄk DvoÅák, Ken-ichi Kawarabayashi,