Packing Independent Cliques in K₄-minor-free Graphs

2025/12/19 by Benjamin Xiao, Xiao, Benjamin, Dong Ye +1
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · doi:10.48550/arxiv.2512.18090

openalex publication_date 2025/12/19 · openalex created_date 2025/12/24 · openalex updated_date 2026/07/28

Abstract

Let G be a graph and S be a set of cliques of G. The set S is an indeque set if every component of G[S], the subgraph induced by vertices of S, is a clique. In this paper, we prove that the indeque ratio of K₄-minor-free graphs is \frac 1 2, which settle two conjectures of Biro, Collado and Zamora. We also show that the indeque ratio of subcubic graphs is \frac 1 2.

Citations

• Packing independent cliques into planar graphs
• On the d-Claw Vertex Deletion Problem
• Independent Chains in Acyclic Posets

Related

• Packing independent cliques into planar graphs
• On independent domination and packing numbers of subcubic graphs
• Dense minors and bipartite independence numbers
• Clique minors in graphs with a forbidden subgraph
• A new method for enumerating independent sets of a fixed size in general graphs