REVIEW 4 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
Graphs with large minimum degree and no small odd cycles are $3$-colourable
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 4 Pith papers
-
On the chromatic profile for tripartite graphs and beyond
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 ...
-
On the chromatic profile for tripartite graphs and beyond
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.
-
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)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.