Tree-chromatic number

Paul Seymour

doi:10.1016/j.jctb.2015.08.002

Tree-chromatic number

Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

Let us say a graph G has "tree-chromatic number" at most k if it admits a tree-decomposition (T, (X_t:t∈V(T))) such that G[X_t] has chromatic number at most k for each 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, every graph with no triangle and with no induced cycle of length more than ℓ has tree-chromatic number at most ℓ-2.

Original language	English (US)
Pages (from-to)	229-237
Number of pages	9
Journal	Journal of Combinatorial Theory. Series B
Volume	116
DOIs	https://doi.org/10.1016/j.jctb.2015.08.002
State	Published - Jan 2016

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Colouring
Induced subgraph
Tree-decomposition

Access to Document

10.1016/j.jctb.2015.08.002

Cite this

@article{72cc03c3ab2e4be0a840fbc1ef7dc379,

title = "Tree-chromatic number",

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))) such that G[Xt] has chromatic number at most k for each 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, every graph with no triangle and with no induced cycle of length more than ℓ has tree-chromatic number at most ℓ-2.",

keywords = "Colouring, Induced subgraph, Tree-decomposition",

author = "Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier Inc.",

year = "2016",

month = jan,

doi = "10.1016/j.jctb.2015.08.002",

language = "English (US)",

volume = "116",

pages = "229--237",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Tree-chromatic number

AU - Seymour, Paul

PY - 2016/1

Y1 - 2016/1

N2 - Let us say a graph G has "tree-chromatic number" at most k if it admits a tree-decomposition (T, (Xt:t∈V(T))) such that G[Xt] has chromatic number at most k for each 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, every graph with no triangle and with no induced cycle of length more than ℓ has tree-chromatic number at most ℓ-2.

AB - Let us say a graph G has "tree-chromatic number" at most k if it admits a tree-decomposition (T, (Xt:t∈V(T))) such that G[Xt] has chromatic number at most k for each 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, every graph with no triangle and with no induced cycle of length more than ℓ has tree-chromatic number at most ℓ-2.

KW - Colouring

KW - Induced subgraph

KW - Tree-decomposition

UR - http://www.scopus.com/inward/record.url?scp=84947581170&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947581170&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2015.08.002

DO - 10.1016/j.jctb.2015.08.002

M3 - Article

AN - SCOPUS:84947581170

SN - 0095-8956

VL - 116

SP - 229

EP - 237

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Tree-chromatic number

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this