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

DOI10.1016/J.AIM.2022.108534zbMATH Open1501.05023arXiv2009.05495OpenAlexW3084441407MaRDI QIDQ2161306FDOQ2161306

Asaf Ferber, Michael Krivelevich

Publication date: 4 August 2022

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Large Induced Subgraphs with All Degrees Odd
• On induced subgraphs with odd degrees
• On induced subgraphs with all degree odd

Cited In (6)

• Distinct degrees and homogeneous sets
• 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
• On induced subgraphs with all degree odd
• A result on large induced subgraphs with prescribed residues in bipartite graphs

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)