A note on Hadwiger's conjecture for path-chromatic number

Hikaru Yokoi

doi:10.47443/dml.2024.186

Author(s)

Hikaru Yokoi Department of Mathematics, Keio University,Yokohama,Japan

Abstract

Let G be a graph and (T, B) be a tree-decomposition of G, where B = (Bt)t?V (T ). The chromatic number of (T, B) is the maximum chromatic number among the subgraphs induced by Bt. The tree-chromatic number of G is the minimum chromatic number of the tree-decompositions of G. Huynh, Reed, Wood, and Yepremyan [2019-20 MATRIX Annals, Springer, Cham, 2021, 489-498] posed a Hadwiger-type conjecture for tree-chromatic number, and asked for a short proof that every K6-minor-free graph has tree-chromatic number at most 5 even if it is allowed to use the Four Color Theorem. The present article answers this question by observing that, assuming Hadwiger's Conjecture for Kp-minor-free graphs, every Kp+1minor-free graph has tree-chromatic number at most p. More precisely, only path-decompositions of graphs are considered.

Publication Details

Page(s) 65-66

DOI 10.47443/dml.2024.186

Published Journal: Discrete Mathematics Letters, Volume: 15, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords

tree-chromatic number, tree-decomposition, Hadwiger's Conjecture, path-chromatic number

References

Appel K. .1977 .Every planar map is four colorable. I. Discharging, Illinois J. , 21 : 429-490.

Appel K. .1977 .Every planar map is four colorable. , 21 : 491-567.

Bondy J. A.,Murty U. S. R. .2008 .. , : .

Hadwiger H. .1943 .. , 88 : 133-142.

Huynh T.,Kim R. .2017 .Tree-chromatic number is not equal to path-chromatic number. J. Graph Theory, 86 : 213-222.

Huynh T.,Reed B.,Wood D. R.,Praeger C. E. .2021 .- and path-chromatic number. MATRIX Annals, : 489-498.

Robertson N.,Seymour P. .1993 .Hadwiger's conjecture for K6-free graphs. Combinatorica, 13 : 279-361.

Seymour P. .2016 .Tree-chromatic number. J. Combin. Theory Ser. B, 116 : 229-237.

Wagner K. .1937 .. , 114 : 570-590.