Subgraphs of large connectivity and chromatic number

DOI10.1112/BLMS.12569zbMATH Open1520.05034arXiv2004.00533OpenAlexW3014398515MaRDI QIDQ6133373FDOQ6133373

Bhargav P. Narayanan, António Girão

Publication date: 18 August 2023

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

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.

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

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

zbMATH Keywords

chromatic numberconnectivitysubgraphslist chromatic number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Subgraphs of large connectivity and chromatic number in graphs of large chromatic number
• Substitution and \(\chi\)-boundedness
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• A relaxed Hadwiger's conjecture for list colorings
• Isolating highly connected induced subgraphs

Cited In (8)

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

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)