Pith. sign in

REVIEW 2 cited by

A strong structural stability of C_(2k+1)-free graphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2408.15487 v2 pith:ISEPBWIK submitted 2024-08-28 math.CO

A strong structural stability of C_(2k+1)-free graphs

classification math.CO
keywords fraclimitsbipartitebigcupchoosegraphlceillfloor
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
read the original abstract

F\"uredi and Gunderson showed that $ex(n, C_{2k+1})$ is achieved only on $K_{\lfloor\frac{n}{2}\rfloor, \lceil\frac{n}{2}\rceil}$ if $n\ge 4k-2$. It is natural to study how far a $ C_{2k+1}$-free graph is from being bipartite.Let $T^*(r, n)$ be obtained by adding a suspension $K_{r}$ with $1$ suspension point to $K_{\lfloor\frac{n-r+1}{2}\rfloor, \lceil\frac{n-r+1}{2}\rceil}$. We show that for integers $r, k$ with $3\le r\le 2k-4$ and $n\ge 20(r+2)^2k$, if $G$ is a $C_{2k+1}$-free $n$-vertex graph with $e(G)\ge e(T^*(r, n))$, then $G$ is obtained by adding suspensions to a bipartite graph one by one and the total number of vertices in all suspensions minus intersection points is no more than $r-1$. In other words, $G=B\bigcup\limits_{i=1}^p G_i$, where $B$ is a bipartite graph, $G_1$ is a suspension to $B$, $G_j$ is a suspension to $B\bigcup\limits_{i=1}^{j-1} G_i$ for $2\le j\le p$ and $\sum\limits_{i=1}^p \vert V(G_i)-V(G_i)\cap V(B\bigcup\limits_{i=1}^{j-1} G_i) \vert\le r-1$. Furthermore, $\sum\limits_{i=1}^p \vert V(G_i)-V(G_i)\cap V(B\bigcup\limits_{i=1}^{j-1} G_i) \vert= r-1$ if and only if $G=T^*(r, n)$. Let $d_2(G)=\min\{|T|: T\subseteq V(G), G-T \ \text{is bipartite}\}$ and $\gamma_2(G)=\min\{|E|: E\subseteq E(G), G-E \ \text{is bipartite}\}$. Our structural stability result implies that $d_2(G)\le r-1$ and $\gamma_2(G)\le {\lceil\frac{r}{2}\rceil \choose 2}+{\lfloor\frac{r}{2}\rfloor \choose 2}$ under the same condition, which is a recent result of Ren-Wang-Wang-Yang [SIAM J. Discrete Math. 38 (2024)]. They proved $d_2(G)\le r-1$ and $\gamma_2(G)\le {\lceil\frac{r}{2}\rceil \choose 2}+{\lfloor\frac{r}{2}\rfloor \choose 2}$ separately. We introduce a new concept strong-$2k$-core which is the key that we can give a stronger structural stability result but a simpler proof.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the chromatic profile for tripartite graphs and beyond

    math.CO 2026-04 unverdicted novelty 8.0

    For all H with χ(H)=3, δ_χ(H,2) belongs to the finite set {1/2, 2/5, 2/7, 1/4, 2/9, 1/5, 2/11, 1/6}, with complete structural characterization of the associated H and an extension to color-critical graphs via the new ...

  2. On the chromatic profile for tripartite graphs and beyond

    math.CO 2026-04 accept novelty 8.0

    For every graph H with χ(H)=3 the possible values of δ_χ(H,2) form the finite set {1/2, 2/5, 2/7, 1/4, 2/9, 1/5, 2/11, 1/6}, with complete structural classification of the realizing graphs H.