A Note on Large Degenerate Induced Subgraphs in Sparse Graphs
Alexander Clow, Sean Kim, Ladislav Stacho · 2025
Read A Note on Large Degenerate Induced Subgraphs in Sparse Graphs by Alexander Clow, Sean Kim, Ladislav Stacho (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13693.txt.
Introduction
Alexander Clow, Sean Kim, and Ladislav Stacho bound the size of large degenerate induced subgraphs inside sparse graphs. A graph is d-degenerate when every part of it holds a vertex of degree at most d, a common sparseness measure. They ask how big an induced d-degenerate piece any k-degenerate graph must contain.
Their lower bound takes the better of two terms, one scaling with the graph's order and one tied to a complementary independence measure. The result improves a classic bound of Alon, Kahn, and Seymour for this setting. A modified argument sharpens the bound further for graphs of bounded genus, extending earlier work that covered only planar graphs.
Catalog record
| CREATOR | Alexander Clow, Sean Kim, Ladislav Stacho |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13693
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Note on Large Degenerate Induced Subgraphs in Sparse Graphs Alexander Clow, Sean Kim, Ladislav Stacho Abstract Given a graph G G and a non-negative integer d d let α d ( G ) \alpha_{d}(G) be the order of a largest induced d d -degenerate subgraph of G G . We prove that for any pair of non-negative integers k > d k>d , if G G is a k k -degenerate graph, then α d ( G ) ≥ max { ( d + 1 ) n k + d + 1 , n − α k − d − 1 ( G ) } \alpha_{d}(G)\geq\max\{\frac{(d+1)n}{k+d+1},n-\alpha_{k-d-1}(G)\} . For k k -degenerate graphs this improves a more general lower bound of Alon, Kahn, and Seymour. By modifying our argument we obtain improved lower bound on α d ( G ) \alpha_{d}(G) for graphs of bounded genus. This extends earlier work on degenerate subgraphs of planar graphs. 1 Introduction A graph G is d -degenerate if every subgraph H of G has minimum degree at most d . The degeneracy of a graph G is the least d such that G is d -degenerate. Thus, a graph is 0 -degenerate if and only if it has no edges, and 1 -degenerate if and only if it is a forests. Given a fixed integer d and a graph G , we let \alpha_{d}(G) be the order of a largest induced d -degenerate subgraph of G . Hence, by setting d=0 one can recover the independence number of the graph G . For more background and definitions in graph theory we refer the reader to [ 23 ] . Alon, Kahn, and Seymour [ 4 ] began the study of \alpha_{d}(G) when they proved that in any graph G , \alpha_{d}(G)\geq\sum_{v\in V(G)}\min\Big\{1,\frac{d+1}{\deg(v)+1}\Big\}. Notice that this bound is tight for any disjoint union of cliques. As remarked in [ 4 ] , when d=0 this returns a classic lower bound for independence number proven by Caro [ 8 ] and independently by Wei [ 22 ] . As a corollary of this result, graphs with average degree D\geq 2d have \alpha_{d}(G)\geq\frac{(d+1)n}{D+1}. Observe that every k -degenerate graph has average degree at most 2k , with equality for any maximally k -degenerate graph. So for any d<k , Alon, Kahn, and Seymour proved that in any k -degenerate graph \alpha_{d}(G)\geq\frac{(d+1)n}{2k+1} . There is a long history of studying \alpha_{d} for planar graphs. As corollary of the Four Colour Theorem, for all planar graphs G , \alpha_{0}(G)\geq\frac{n}{4} . This bound is tight as witnessed by K_{4} . Proving this lower bound without the Four Colour Theorem remains open, although there has been some progress, see [ 3 , 10 ] . Similarly, K_{4} demonstrates that there are planar graphs with \alpha_{1}(G)=\frac{n}{2} . Albertson and Berman [ 2 ] and Akiyama and Watanabe [ 1 ] independently conjectured that \alpha_{1}(G)\geq\frac{n}{2} for all planar graphs. This conjecture has seen some significant attention since being proposed. Indeed, a corollary of Borodin’s proof [ 6 ] that all planar graphs are acyclically 5 -colourable is that for all planar graphs G , \alpha_{1}(G)\geq\frac{2n}{5} . This remains the best general lower bound on \alpha_{1} for planar graphs. The conjecture is known to be true for triangle-free planar graphs, see [ 21 ] . The current best lower bound on \alpha_{1} for triangle-free planar graphs G is from Dross, Montassier, and Pinlou [ 11 ] who proved that \alpha_{1}(G)\geq\frac{6n+7}{11} . More recently, studying \alpha_{d} for 2\leq d\leq 4 in planar graphs has garnered some attention. The octahedron witnesses that there exists planar graphs with \alpha_{2}(G)=\frac{2n}{3} . Gu, Kierstead, Oum, Qi, and Zhu [ 13 ] conjecture that every planar graph has \alpha_{2}(G)\geq\frac{2n}{3} . Notably, Dvořák and Kelly [ 12 ] proved that if G is a triangle-free planar graph then the stronger bound \alpha_{2}(G)\geq\frac{4n}{5} holds. When d=3 the octahedron and icosahedron witness that there exists planar graphs with \alpha_{3}(G)=\frac{5n}{6} . Gu, Kierstead, Oum, Qi, and Zhu [ 13 ] showed that all planar graphs have \alpha_{3}(G)\geq\frac{3n}{4} . For d=4 the icosahedron witnesses that there exists planar graphs with \alpha_{4}(G)=\frac{11n}{12} . The best bound here is from Lukot’ka, Mazák, and Zhu [ 16 ] who showed that for all planar graphs \alpha_{4}(G)\geq\frac{8n}{9} . In this paper, we consider this problem for k -degenerate graphs. Thus, our results are for a more general class of graphs than planar graphs, but more specific than the average degree cases studied in [ 4 ] . Our primary contribution is the following theorem. Theorem 1.1 . Let k>d be non-negative integers. If G is a k -degenerate graph, then \alpha_{d}(G)\geq\max\Big\{\frac{(d+1)n}{k+d+1},n-\alpha_{k-d-1}(G)\Big\}. Furthermore, V(G) can be partitioned into sets X and Y such that G[X] is d -degenerate and G[Y] is (k-d-1) -degenerate. Since Theorem 1.1 provides linear lower bound on \alpha_{d} , for pairs of integers k>d , we define \alpha_{d}(k):=\inf_{G\text{ with degeneracy $k$}}\frac{\alpha_{d}(G)}{|V(G)|}, and note that \alpha_{d}(k) is bounded away from 0 . Trivially, as witnessed by the clique K_{k+1} , for all k>d , \alpha_{d}(k)\leq\frac{d+1}{k+1} . Together with Theorem 1.1 this implies \frac{2}{k+2}\leq\alpha_{1}(k)\leq\frac{2}{k+1} for all k . Meaning that for large k our bound in Theorem 1.1 is close to optimal. On the other hand as d grows relative to k , our lower bound that \alpha_{d}(G)\geq\frac{(d+1)n}{k+d+1} tends to Alon, Kahn, and Seymour’s bound for graphs with average degree at most 2k . In these cases, the other term in our lower bound can be helpful. For example, Theorem 1.1 implies that if G is k -degenerate and the independence number of G is \frac{n}{k+1} , the minimum for maximally k -degenerate graphs, then \alpha_{d}(G)\geq\frac{(d-1)n}{k+1} . This nearly matches the \alpha_{d}(k) upper bound witnessed by cliques. Notice that for certain values of k and d , for example k=3 and d=1 , \alpha_{d}(k)=\frac{d+1}{k+1} , while for other values of k and d , for example k=2 and d=1 , \alpha_{d}(k)<\frac{d+1}{k+1} . To see that \alpha_{1}(3)=\frac{1}{2} notice that Theorem 1.1 implies \alpha_{1}(G)\geq n-\alpha_{1}(G) for any 3 -degenerate graph G . Meanwhile, K_{4} with one edge subdivided is an example of 2 -degenerate graph that witnesses \alpha_{1}(2)\leq\frac{3}{5}<\frac{2}{3} . Given the literature on planar graphs, studying this problem for graphs of bounded genus is natural. For a preliminary on graphs on more general surfaces than the plane we recommend [ 19 ] . By adapting our proof of Theorem 1.1 we obtain the following bound for graphs of bounded genus. Theorem 1.2 . Let g be an integer. If G is a graph with genus at most g , then • \alpha_{1}(G)\geq\frac{2n-24g+2}{7} , and • \alpha_{2}(G)\geq\frac{n-2g+4}{3} , and • \alpha_{3}(G)\geq\frac{n}{2}-g+1 , and • \alpha_{4}(G)\geq\frac{3n-2g+4}{5} , and • \alpha_{5}(G)\geq\frac{2n-g+2}{3} . Recalling that for planar graphs, the best lower bound on \alpha_{1} comes from acyclic colouring, we note that this approach an acyclic colouring argument does not improve Theorem 1.2 in the d=1 case for graphs with larger genus. This is because there are graphs with genus g and acyclic chromatic number \Omega(g^{\frac{4}{7}-o(1)}) , see [ 5 ] . Even if we restrict to locally planar graphs, which are the classic example of graphs of large genus that behave like planar graphs, one does not