Highly Connected Subgraphs with Large Chromatic Number
Tung H. Nguyen · SIAM Journal on Discrete Mathematics · 2024
Abstract. For integers [Formula: see text] and [Formula: see text], let [Formula: see text] be the least integer [Formula: see text] such that every graph with chromatic number at least [Formula: see text] contains a [Formula: see text]-connected subgraph with chromatic number at least [Formula: see text]. Refining the recent result of Girão and Narayanan [ Bull. Lond. Math. Soc., 54 (2022), pp. 868–875] that [Formula: see text] for all [Formula: see text], we prove that [Formula: see text] for all [Formula: see text] and [Formula: see text]. This sharpens earlier results of Alon et al. [ J. Graph Theory, 11 (1987), pp. 367–371], of Chudnovsky [ J. Combin. Theory Ser. B, 103 (2013), pp. 567–586], and of Penev, Thomassé, and Trotignon [ SIAM J. Discrete Math., 30 (2016), pp. 592–619]. Our result implies that [Formula: see text] for all [Formula: see text], making a step closer towards a conjecture of Thomassen [ J. Graph Theory, 7 (1983), pp. 261–271] that [Formula: see text], which was originally a result with a false proof and was the starting point of this research area.