Isolating highly connected induced subgraphs

DOI10.1137/140981939MaRDI QIDQ2801334zbMATH OpenOpenAlexFDO

Authors Irena Penev, Stéphan Thomassé, Nicolas Trotignon

Publication date 7 April 2016

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

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

zbMATH Keywords

chromatic numberconnectivityextreme decomposition theoremhereditary classes of graphsoperations on graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Connectivity (05C40) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We prove that any graph $G$ of minimum degree greater than $2k^2-1$ has a $(k+1)$-connected induced subgraph $H$ such that the number of vertices of $H$ that have neighbors outside of $H$ is at most $2k^2-1$. This generalizes a classical result of Mader, which states that a high minimum degree implies the existence of a highly connected subgraph. We give several variants of our result, and for each of these variants, we give asymptotics for the bounds. We also we compute optimal values for the case when $k=2$. Alon, Kleitman, Saks, Seymour, and Thomassen proved that in a graph of high chromatic number, there exists an induced subgraph of high connectivity and high chromatic number. We give a new proof of this theorem with a better bound.

Recommendations

• Highly connected subgraphs of graphs with given independence number
• Highly connected subgraphs of graphs with given independence number (extended abstract)
• Large Induced Subgraphs with All Degrees Odd
• Partitions of graphs with high minimum degree or connectivity.
• Forcing highly connected subgraphs

Cites work

• Dynamic cage survey
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Subgraphs of large connectivity and chromatic number in graphs of large chromatic number
• Substitution and \(\chi\)-boundedness

Cited in

(11)

• Highly connected subgraphs of graphs with given independence number
• Edge-disjoint induced subgraphs with given minimum degree
• Clique cutsets beyond chordal graphs
• Forcing highly connected subgraphs
• Highly connected subgraphs of graphs with given independence number (extended abstract)
• Unavoidable Induced Subgraphs of Large 2-Connected Graphs
• Subgraphs of large connectivity and chromatic number
• Highly Connected Subgraphs with Large Chromatic Number
• Polynomial bounds for chromatic number. VIII: Excluding a path and a complete multipartite graph
• Graph theory. Abstracts from the workshop held January 5--10, 2025
• Isolation concepts for efficiently enumerating dense subgraphs

This page was built for publication: Isolating highly connected induced subgraphs

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