Tree-chromatic number

Research output: Contribution to journalArticle

5 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)229-237
Number of pages9
JournalJournal of Combinatorial Theory. Series B
Volume116
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Tree-chromatic number'. Together they form a unique fingerprint.

  • Cite this