Odd Induced Subgraphs in Graphs of Maximum Degree Four
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914164390232064 |
|---|---|
| author | Ai, Jiangdong Guo, Qiwen Gutin, Gregory Hao, Yiming Yeo, Anders |
| author_facet | Ai, Jiangdong Guo, Qiwen Gutin, Gregory Hao, Yiming Yeo, Anders |
| contents | A graph is called odd if all of its vertex degrees are odd. A long-standing conjecture asked whether there exists a positive constant $c$ such that every $n$-vertex graph without isolated vertices contains an odd induced subgraph on at least $cn$ vertices. In 2022, Ferber and Krivelevich resolved this conjecture affirmatively with $c=10^{-4}$. A natural question is to determine the largest possible constant $c$. In 1994, Caro remarked that if $2/7$ is a valid value for $c$, then it is the largest possible one. To the best of our knowledge, the bound $c\ge 2/7$ has not been improved. Previous research has established tight bounds for specific graph classes -- for instance, $c = 2/5$ for graphs with maximum degree at most $3$ and without isolated vertices. In this paper, we prove that $c=2/7$ is the tight bound for graphs with maximum degree at most $4$ and without isolated vertices. Our result provides some support for $2/7$ being the largest value of $c$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15489 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Odd Induced Subgraphs in Graphs of Maximum Degree Four Ai, Jiangdong Guo, Qiwen Gutin, Gregory Hao, Yiming Yeo, Anders Combinatorics 05C35 (Primary), 05C07 (Secondary) A graph is called odd if all of its vertex degrees are odd. A long-standing conjecture asked whether there exists a positive constant $c$ such that every $n$-vertex graph without isolated vertices contains an odd induced subgraph on at least $cn$ vertices. In 2022, Ferber and Krivelevich resolved this conjecture affirmatively with $c=10^{-4}$. A natural question is to determine the largest possible constant $c$. In 1994, Caro remarked that if $2/7$ is a valid value for $c$, then it is the largest possible one. To the best of our knowledge, the bound $c\ge 2/7$ has not been improved. Previous research has established tight bounds for specific graph classes -- for instance, $c = 2/5$ for graphs with maximum degree at most $3$ and without isolated vertices. In this paper, we prove that $c=2/7$ is the tight bound for graphs with maximum degree at most $4$ and without isolated vertices. Our result provides some support for $2/7$ being the largest value of $c$. |
| title | Odd Induced Subgraphs in Graphs of Maximum Degree Four |
| topic | Combinatorics 05C35 (Primary), 05C07 (Secondary) |
| url | https://arxiv.org/abs/2511.15489 |