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 numberconnectivityhereditary classes of graphsoperations on graphsextreme decomposition theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) 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

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

Cited in

(9)

• Highly Connected Subgraphs with Large Chromatic Number
• Unavoidable Induced Subgraphs of Large 2-Connected Graphs
• Highly connected subgraphs of graphs with given independence number
• Polynomial bounds for chromatic number. VIII: Excluding a path and a complete multipartite graph
• Clique cutsets beyond chordal graphs
• Isolation concepts for efficiently enumerating dense subgraphs
• Subgraphs of large connectivity and chromatic number
• Highly connected subgraphs of graphs with given independence number (extended abstract)
• Edge-disjoint induced subgraphs with given minimum degree

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)