Tree-Chromatic Number Is Not Equal to Path-Chromatic Number*

Tony Huynh, Ringi Kim

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

For a graph G and a tree-decomposition (T,B) of G, the chromatic number of (T,B) is the maximum of χ(G[B]), taken over all bags B∈B. The tree-chromatic number of G is the minimum chromatic number of all tree-decompositions (T,B) of G. The path-chromatic number of G is defined analogously. In this article, we introduce an operation that always increases the path-chromatic number of a graph. As an easy corollary of our construction, we obtain an infinite family of graphs whose path-chromatic number and tree-chromatic number are different. This settles a question of Seymour (J Combin Theory Ser B 116 (2016), 229–237). Our results also imply that the path-chromatic numbers of the Mycielski graphs are unbounded.

Original languageEnglish
Pages (from-to)213-222
Number of pages10
JournalJournal of Graph Theory
Volume86
Issue number2
DOIs
Publication statusPublished - 1 Oct 2017
Externally publishedYes

Keywords

  • chromatic number
  • Mycielski graphs
  • path-decompositions
  • tree-decompositions

Cite this