Notes on tree- and path-chromatic number

DOI10.1007/978-3-030-62497-2_30MaRDI QIDQ2058953zbMATH OpenOpenAlexFDO

Authors Tony Huynh, David R. Wood, L. Yepremyan, Bruce Reed

Publication date 10 December 2021

Full work available at URL https://arxiv.org/abs/2002.05363

zbMATH Keywords

\(k\)-colourable graphHadwiger's conjecture

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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 $K_5$-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.

Recommendations

• Tree-chromatic number
• Tree-chromatic number is not equal to path-chromatic number
• Separating tree-chromatic number from path-chromatic number
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• Excluding any graph as a minor allows a low tree-width 2-coloring

Cites work

• A Ramsey theorem for trees
• Computing Pathwidth Faster Than 2 n
• Graph Theory and Probability
• Hadwiger's conjecture
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• scientific article; zbMATH DE number 3262991 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Layered separators in minor-closed graph classes with applications
• On the hardness of approximating minimization problems
• On the hardness of approximating the chromatic number
• Separating tree-chromatic number from path-chromatic number
• Set partitioning via inclusion-exclusion
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Sur le coloriage des graphs
• Tree-chromatic number
• Tree-chromatic number is not equal to path-chromatic number
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(6)

• Separating tree-chromatic number from path-chromatic number
• The colour lemma. A combinatorial result and its application to tree partitions
• A note on induced subtrees and chromatic number of graphs
• Tree-chromatic number is not equal to path-chromatic number
• A note on Hadwiger's conjecture for path-chromatic number
• Tree-chromatic number

This page was built for publication: Notes on tree- and path-chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2058953)