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

CREATORAlexander Clow, Sean Kim, Ladislav Stacho
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text