2022/06/01 by Tung H. Nguyen, Nguyen, Tung H. · 2 citations
Mathematics · Computer Science · Engineering · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2206.00561
For integers k≥1 and m≥2, let g(k,m) be the least integer n≥1 such that every graph with chromatic number at least n contains a (k+1)-connected subgraph with chromatic number at least m. Refining the recent result Girão and Narayanan that g(k-1,k)≤ 7k+1 for all k≥2, we prove that g(k,m)≤ max(m+2k-2,\lceil(3+(1)/(16))k\rceil) for all k≥1 and m≥2. This sharpens earlier results of Alon, Kleitman, Saks, Seymour, and Thomassen, of Chudnovsky, Penev, Scott, and Trotignon, and of Penev, Thomassé, and Trotignon. Our result implies that g(k,k+1)≤\lceil(3+(1)/(16))k\rceil for all k≥1, making a step closer towards a conjecture of Thomassen from 1983 that g(k,k+1)≤ 3k+1, which was originally a result with a false proof and was the starting point of this research area.