Skip to content
DraconiticResearch
Search Sources API
197,357 studies31 sourcesUpdated 20 min ago
PreprintarXiv licencearXiv

Polynomial minimum degree stability for $3$-chromatic graphs

  • Yisai Xue
Open at sourcePDFDOICite

Abstract

Let H be a fixed 3-chromatic graph, and let g ≥ 2 be the smallest integer such that there is no homomorphism H → C2 g+1. For every ε>0, we prove that there exists a constant ρ>0 such that every H-free n-vertex graph G with δ(G) ≥(2 /(2 g+1)+ε) n can be made bipartite by deleting O(n2−ρ) edges. Thus the sharp qualitative minimum-degree stability theorem for 3-chromatic graphs admits a polynomial strengthening. In particular, this gives an affirmative answer to a question of Illingworth [\textit{Minimum degree stability of H-free graphs}, Combinatorica, 43(1):129-147, 2023.] on blow-ups of odd cycles.

Related

  1. Bounded chromatic number of graphs with small clique number and large minimum degree
    Jiaao Li, Xinyuan Li
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Positive Square Energy of Graphs with Minimum Degree at Least Two
    S. Akbari, Fu-Tao Hu, Ya-Yang Liu
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  3. An improved minimum degree threshold for fractional clique decompositions in partite graphs
    Sean Longbrake, Michael Simkin, Liana Yepremyan +1
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. On the minimum number of triangles in balanced tripartite graphs with large minimum degree
    Chunqiu Fang, Rongxing Xu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Explicit M-polynomial and degree-based topological indices of Hanoi graphs
    El-Mehdi Mehiri
    Discrete Applied MathematicsPeer-reviewedLicence not statedFull text2 citedTheoretical & computational chemistryCombinatorics & discrete mathematicsHAL

Cite

BibTeXRIS
BibTeX
@misc{xue2026polynomial,
  title = {{Polynomial minimum degree stability for $3$-chromatic graphs}},
  author = {Yisai Xue},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2606.07358},
  eprint = {2606.07358},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.07358},
}
RIS
TY  - UNPB
TI  - Polynomial minimum degree stability for $3$-chromatic graphs
AU  - Yisai Xue
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2606.07358
UR  - https://arxiv.org/abs/2606.07358
AB  - Let H be a fixed 3-chromatic graph, and let g ≥ 2 be the smallest integer such that there is no homomorphism H → C_2 g+1. For every ε>0, we prove that there exists a constant ρ>0 such that every H-free n-vertex graph G with δ(G) ≥(2 /(2 g+1)+ε) n can be made bipartite by deleting O(n^2−ρ) edges. Thus the sharp qualitative minimum-degree stability theorem for 3-chromatic graphs admits a polynomial strengthening. In particular, this gives an affirmative answer to a question of Illingworth [\textit{Minimum degree stability of H-free graphs}, Combinatorica, 43(1):129-147, 2023.] on blow-ups of odd cycles.
ER  -