Notes on Tree- and Path-Chromatic Number

Tony Huynh, Bruce A Reed, David R Wood, Liana Yepremyan

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

Abstract

Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic number is defined analogously. These parameters were introduced by Seymour [JCTB 2016]. In this paper, we survey all the known results on tree- and path-chromatic number and then present some new results and conjectures. In particular, we propose a version of Hadwiger’s Conjecture for tree chromatic number. As evidence that our conjecture may be more tractable than Hadwiger’s Conjecture, we give a short proof that every K5-minor-free graph has tree-chromatic number at most 4, which avoids the Four Colour Theorem. We also present some hardness results and conjectures for computing tree- and path chromatic number.
Original languageEnglish
Title of host publication2019-20 MATRIX Annals
EditorsDavid R Wood, Jan de Gier, Cheryl E Praeger, Terence Tao
Place of PublicationCham Switzerland
PublisherSpringer
Pages489-498
Number of pages10
Volume4
Edition1
ISBN (Electronic)9783030624972
ISBN (Print)9783030624965
DOIs
Publication statusPublished - 2021

Publication series

NameMATRIX Book Series
PublisherSpringer
Number1
Volume4
ISSN (Print)2523-3041
ISSN (Electronic)2523-305X

Cite this