REVIEW 3 cited by
Graphs with large minimum degree and no small odd cycles are $3$-colourable
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
abstract
Answering a question by Letzter and Snyder, we prove that for large enough $k$ any $n$-vertex graph $G$ with minimum degree at least $\frac{1}{2k-1}n$ and without odd cycles of length less than $2k+1$ is $3$-colourable. In fact, we prove a stronger result that works with a slightly smaller minimum degree.
Forward citations
Cited by 3 Pith papers
-
Interpolating chromatic and homomorphism thresholds
The authors determine the exact VC-dimension-interpolated homomorphism thresholds for cliques and prove the blowup threshold of odd cycles C_{2k-1} is 1/(2k-1).
-
On the spectrum and structure of blowup thresholds
Blowup thresholds are always positive for non-bipartite H, fail monotonicity under induced subgraphs, and equal 1/4 for certain constrained odd-cycle blowups.
-
On the structure of dense graphs with given odd girth
Every n-vertex graph with odd girth at least 2k+1 and minimum degree greater than 4n/(6k−1) is homomorphic to the Möbius ladder M_{4k}.
Discussion (0). Continue with ORCID to comment.