A simplified proof of the Johansson-Molloy Theorem using the Rosenfeld counting method

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 2111.06214 v1 pith:2QHN63MV submitted 2021-11-11 math.CO

Anders Martinsson This is my paper · ORCID

classification math.CO

keywords deltachromaticcountingdegreegraphjohansson-molloyleftmaximum

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

abstract

We show that any triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\left(1+o(1)\right)\Delta/\log \Delta.$

Forward citations

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

Triangle-free $d$-degenerate graphs have small fractional chromatic number
math.CO 2025-01 accept novelty 8.0 of 10

Every triangle-free d-degenerate graph has fractional chromatic number at most (4+o(1))d/ln d, confirming Harris's conjecture.