PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
May 3, 20240 citationsOpen Access

Unavoidable induced subgraphs in graphs with complete bipartite induced minors

View Full Paper
MCMaria ChudnovskyMHMeike HatzelTKTuukka Korhonen

Key Points

Key points are not available for this paper at this time.

Abstract

We prove that if a graph contains the complete bipartite graph K₁₃₄, ₁₂ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contains K₃, ₄ as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a theta is a graph made of three internally vertex-disjoint chordless paths P₁ = a b, P₂ = a b, P₃ = a b, each of length at least two, such that no edges exist between the paths except the three edges incident to a and the three edges incident to b. A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number, or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels).

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Chudnovsky et al. (2024) studied this question.

synapsesocial.com/papers/68e6bbccb6db64358763c3d7https://doi.org/10.48550/arxiv.2405.01879
Ask AI
Helpful
Bookmark
Share
View Full Paper