Every graph contains a linearly sized induced subgraph with all degrees odd

DOI10.1016/J.AIM.2022.108534MaRDI QIDQ2161306zbMATH OpenOpenAlexFDO

Authors Asaf Ferber, Michael Krivelevich

Publication date 4 August 2022

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.05495

zbMATH Keywords

odd subgraphsCaro's conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that every graph $G$ on $n$ vertices with no isolated vertices contains an induced subgraph of size at least $n/10000$ with all degrees odd. This solves an old and well-known conjecture in graph theory.

Recommendations

• On induced subgraphs with odd degrees
• Large Induced Subgraphs with All Degrees Odd
• Every tree contains a large induced subgraph with all degrees odd
• On induced subgraphs of trees, with restricted degrees
• Odd induced subgraphs in planar graphs with large girth

Cites work

• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• Large Induced Subgraphs with All Degrees Odd
• On induced subgraphs with all degree odd
• On induced subgraphs with odd degrees

Cited in

(8)

• Distinct degrees and homogeneous sets
• Odd induced subgraphs in planar graphs with large girth
• Odd induced subgraphs in graphs with treewidth at most two
• On induced subgraphs with odd degrees
• On subgraphs with degrees of prescribed residues in the random graph
• Maximum odd induced subgraph of a graph concerning its chromatic number
• A result on large induced subgraphs with prescribed residues in bipartite graphs
• On induced subgraphs with all degree odd

This page was built for publication: Every graph contains a linearly sized induced subgraph with all degrees odd

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2161306)