Isolating highly connected induced subgraphs

DOI10.1137/140981939zbMATH Open1333.05169arXiv1406.1671OpenAlexW3101066016MaRDI QIDQ2801334FDOQ2801334

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Dynamic cage survey
• 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

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
• Edge-disjoint induced subgraphs with given minimum degree
• Highly connected subgraphs of graphs with given independence number (extended abstract)

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)