Highly Connected Subgraphs with Large Chromatic Number

DOI10.1137/22M150040XMaRDI QIDQ6141860zbMATH OpenOpenAlexFDO

Authors Tung H. Nguyen

Publication date 23 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberconnectivitysubgraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Connectivity (05C40)

Abstract: For integers $kge1$ and $mge2$, let $g(k,m)$ be the least integer $nge1$ 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~ao and Narayanan that $g(k-1,k)le7k+1$ for all $kge2$, we prove that $g(k,m)lemax(m+2k-2,lceil(3+frac116)kceil)$ for all $kge1$ and $mge2$. This sharpens earlier results of Alon, Kleitman, Saks, Seymour, and Thomassen, of Chudnovsky, Penev, Scott, and Trotignon, and of Penev, Thomass'{e}, and Trotignon. Our result implies that $g(k,k+1)lelceil(3+frac116)kceil$ for all $kge1$, making a step closer towards a conjecture of Thomassen from 1983 that $g(k,k+1)le3k+1$, which was originally a result with a false proof and was the starting point of this research area.

Recommendations

• Subgraphs of large connectivity and chromatic number
• Highly connected monochromatic subgraphs
• Note on highly connected monochromatic subgraphs in 2-colored complete graphs
• Highly connected monochromatic subgraphs of two-colored complete graphs
• Isolating highly connected induced subgraphs

Cites work

• A survey of -boundedness
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Graph decomposition with applications to subdivisions and path systems modulo k
• Graph theory
• scientific article; zbMATH DE number 3627227 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Isolating highly connected induced subgraphs
• On the number of edges in a graph with no \((k + 1)\)-connected subgraphs
• Progress towards Nash-Williams' conjecture on triangle decompositions
• Subgraphs of large connectivity and chromatic number
• Subgraphs of large connectivity and chromatic number in graphs of large chromatic number
• Substitution and \(\chi\)-boundedness

Cited in

(4)

• Polynomial bounds for chromatic number. VIII: Excluding a path and a complete multipartite graph
• The weak version of the graph complement conjecture and partial results for the delta conjecture
• Graphs without a 3-connected subgraph are 4-colourable
• Reducing linear Hadwiger's conjecture to coloring small graphs

This page was built for publication: Highly Connected Subgraphs with Large Chromatic Number

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