2025/09/01 by Jiangdong Ai, Ai, Jiangdong, Qiwen Guo +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2509.01428
openalex publication_date 2025/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A long-standing conjecture of Caro (Discrete Math, 1994), confirmed by Ferber and Krivelevich (Adv Math, 2022), states that every n-vertex graph G without isolated vertices contains an induced subgraph of order linear in n in which every vertex has odd degree. We generalize this result to graphs G whose vertices are labeled by ℓ: V(G)→ \0,1\. We require, in an induced subgraph, all 0-labeled vertices to have even degree and all 1-labeled vertices to have odd degree. Let hℓ(G) denote the maximum order of such a subgraph. Let foe(G)=minℓ hℓ(G) be the worst-labeling parameter. We establish a pointwise lower bound for hℓ(G) that immediately yields a linear lower bound in |V(G)| for foe(G), where G has no isolated vertices. For an n-vertex connected graph, we obtain a sharp lower bound for foe(G): foe(G)≥ \lceil (n-1)/χmm(G) \rceil , where χmm(G) is the maximum chromatic number of a minor of G. Using proved cases of Hadwiger's Conjecture, we show that for t∈ \3,4,5,6\, if an n-vertex connected graph G is Kt-minor-free, then foe(G)≥ \lceil (n-1)/(t-1)\rceil and this bound is sharp for each t∈ \3,4,5,6\. Finally, we conjecture that foe(G)≥ fo(G)/2 for all graphs G and confirm the conjecture for all trees and complete multipartite graphs.