| Article ID | Journal | Published Year | Pages | File Type | 
|---|---|---|---|---|
| 4656687 | Journal of Combinatorial Theory, Series B | 2016 | 9 Pages | 
Abstract
												Let us say a graph G has “tree-chromatic number” at most k if it admits a tree-decomposition (T,(Xt:t∈V(T)))(T,(Xt:t∈V(T))) such that G[Xt]G[Xt] has chromatic number at most k for each t∈V(T)t∈V(T). This seems to be a new concept, and this paper is a collection of observations on the topic. In particular we show that there are graphs with tree-chromatic number two and with arbitrarily large chromatic number; and for all ℓ≥4ℓ≥4, every graph with no triangle and with no induced cycle of length more than ℓ has tree-chromatic number at most ℓ−2ℓ−2.
Related Topics
												
													Physical Sciences and Engineering
													Mathematics
													Discrete Mathematics and Combinatorics
												
											Authors
												Paul Seymour, 
											