Subgraphs of large connectivity and chromatic number

DOI10.1112/BLMS.12569MaRDI QIDQ6133373zbMATHOpenAlexFDO

Authors António Girão, Bhargav P. Narayanan

Publication date 18 August 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberconnectivitysubgraphslist chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: Resolving a problem raised by Norin, we show that for each $kinmathbbN$, there exists an $f(k)le7k$ such that every graph $G$ with chromatic number at least $f(k)+1$ contains a subgraph $H$ with both connectivity and chromatic number at least $k$. This result is best-possible up to multiplicative constants, and sharpens earlier results of Alon-Kleitman-Thomassen-Saks-Seymour from 1987 showing that $f(k)=O(k^3)$, and of Chudnovsky-Penev-Scott-Trotignon from 2013 showing that $f(k)=O(k^2)$. Our methods are robust enough to handle list colouring as well: we also show that for each $kinmathbbN$, there exists an $f_{e}ll(k)le4k$ such that every graph $G$ with list chromatic number at least $f_{e}ll(k)+1$ contains a subgraph $H$ with both connectivity and list chromatic number at least $k$. This result is again best-possible up to multiplicative constants; here, unlike with $f(cdot)$, even the existence of $f_{e}ll(cdot)$ appears to have been previously unknown.

Recommendations

• On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
• Isolating highly connected induced subgraphs
• Connectivity and choosability of graphs with no \(K_t\) minor
• Improved lower bound for the list chromatic number of graphs with no K_t minor
• Strengthening Hadwiger's Conjecture

Cites work

• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• A relaxed Hadwiger's conjecture for list colorings
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Isolating highly connected induced subgraphs
• Subgraphs of large connectivity and chromatic number in graphs of large chromatic number
• Substitution and \(\chi\)-boundedness

Cited in

(9)

• Coloring hypergraphs with excluded minors
• On \(k\)-chromatically connected graphs
• Subgraphs with a large cochromatic number
• Highly Connected Subgraphs with Large Chromatic Number
• Acyclic subgraphs with high chromatic number
• Subgraphs with large degrees and girth
• Polynomial bounds for chromatic number. VIII: Excluding a path and a complete multipartite graph
• On graphs with small subgraphs of large chromatic number
• Connectivity and choosability of graphs with no \(K_t\) minor

This page was built for publication: Subgraphs of large connectivity and chromatic number

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