Skip to main content

Tree-chromatic number

Author(s): Seymour, Paul D.

To refer to this page use:
Abstract: Let us say a graph G has “tree-chromatic number” at most k if it admits a tree-decomposition (T, (X-t : t is an element of V (T))) such that G[X-t] has chromatic number at most k for each t is an element of 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 l >= 4, every graph with no triangle and with no induced cycle of length more than E has tree-chromatic number at most l - 2. (C) 2015 Elsevier Inc. All rights reserved.
Publication Date: Jan-2016
Electronic Publication Date: 21-Aug-2015
Citation: Seymour, Paul. (2016). Tree-chromatic number. JOURNAL OF COMBINATORIAL THEORY SERIES B, 116 (229 - 237. doi:10.1016/j.jctb.2015.08.002
DOI: doi:10.1016/j.jctb.2015.08.002
ISSN: 0095-8956
EISSN: 1096-0902
Pages: 229 - 237
Type of Material: Journal Article
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.