A note on Hadwiger's conjecture for path-chromatic number | [Discrete Mathematics Letters • 2025]

Author(s):

1. 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.

Page(s): 65-66

DOI: 10.47443/dml.2024.186

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

Keywords:

treechromatic number , treedecomposition , Hadwigers Conjecture , pathchromatic number

References:

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

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

[3] Bondy J. A.,Murty U. S. R. .2008 .. , : .

[4] Hadwiger H. .1943 .. , 88 : 133-142.

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

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

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

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

[9] Wagner K. .1937 .. , 114 : 570-590.

Citations

Citations are not available for this document.

Citations

Downloads

Views