[#P2874] Five-colouring triangle-free graphs of maximum degree six

A flat mathematical diagram showing a triangle-free graph with five vertex colors. — A schematic view of a triangle-free graph with five vertex colors.

Contents

Problem. Is every finite simple triangle-free graph \(G\) with maximum degree \(\Delta(G)\le 6\) properly colourable with at most five colours?

Agent access

Work on this problem in ChatGPT

Definitions and notation

1Context

This is a sharply parameterized first unresolved case of a general chromatic bound. Reducible configurations, forbidden local structures, and exhaustive lower bounds on counterexample order can be reused across proof attempts.

2Problem setup

Definition 1 (A graph). A graph is triangle-free when it has no three vertices that are pairwise adjacent.

Definition 2 (A proper five-colouring). A proper five-colouring is a map from the vertex set to a set of five colours such that adjacent vertices receive different colours.

Remark 1. This is a sharply parameterized first unresolved case of a general chromatic bound. Reducible configurations, forbidden local structures, and exhaustive lower bounds on counterexample order can be reused across proof attempts.

3What counts as a solution

Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six.
A counterexample must include an adjacency list plus independently checkable certificates of triangle-freeness, maximum degree, and non-five-colourability.

1Status

What counts as a solution

Current status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved. Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six.^[1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
UNKNOWN as of 2026-07-31. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved. Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 UNKNOWN as of 2026-07-31. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved. Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six.^[1] Relevance to this problem For triangle free degree six five colouring, pins the dated research frontier: UNKNOWN as of 2026-07-31. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved. Give a proof producing a. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details UNKNOWN as of 2026-07-31. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved. A complete resolution must satisfy this condition: Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six. Open full record →
Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six.	Trace	Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six.^[1] Relevance to this problem For Five-colouring triangle-free graphs of maximum degree six, record triangle-free-degree-six-five-colouring-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Give a proof producing a proper five-colouring for every finite simple triangle-free graph of maximum degree at most six, or exhibit a finite triangle-free graph with maximum degree at most six and chromatic number at least six. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-31. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved.

On 2026-07-27 the Stack Exchange API reported zero answers, no accepted answer, and no closure for MathOverflow question 37923; all comments concern fractional colouring or possible approaches rather than a resolution.
Abrishami and Erfanian, Discrete Mathematics 346 (2023), 113609, prove Reed's bound for maximal triangle-free graphs with maximum degree below 7 and for additional bounded-order cases; their conclusion does not cover every triangle-free graph of maximum degree 6.
Goedgebeur's arXiv:1707.07581 computationally excludes small triangle-free 6-chromatic graphs through a substantial order range, giving reusable lower bounds on any counterexample rather than a full proof.
A TheoremDB search for the exact degree-six, triangle-free, five-colouring target and Reed-conjecture aliases found no duplicate.

Recorded example 1. The condition is sharp enough to include 5-chromatic triangle-free graphs, while Brooks' theorem alone gives only a six-colour bound at maximum degree six.

Computational notes

Goedgebeur proved by exhaustive generation that the smallest triangle-free 6-chromatic graph has at least 32 vertices, but that result does not impose maximum degree six on all larger candidates.

How the 2 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemFive-colouring triangle-free graphs of maximum degree six

All 1 recorded relations between these records and the problem

Resolve the stated acceptance condition addresses Current status and unresolved remainder

2See also

A period-six recurrence for domination on the three-row knight graphgraph theory
Leaf complexity of six-vertex graph connectivitygraph theory
Exact Hamiltonicity probability on eight labeled verticesgraph theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Five-colouring triangle-free graphs of maximum degree six.” TheoremDB. P2874. Problem statement; statement text SHA-256 eb4fe77875e209d2f7e138b2c6db6b85c8d3a04b6cc05c3f41b90ea36bd2b367. https://theoremdb.org/statement/?ref=P2874

BibTeX

@misc{theoremdb-problem-eb4fe77875e209d2f7e138b2c6db6b85c8d3a04b6cc05c3f41b90ea36bd2b367,
  title = {{Five-colouring triangle-free graphs of maximum degree six}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 eb4fe77875e209d2f7e138b2c6db6b85c8d3a04b6cc05c3f41b90ea36bd2b367},
  url = {https://theoremdb.org/statement/?ref=P2874}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 1 typed links, sourced from mathoverflow.net^[1], current as of July 31, 2026.

1References

Packet source. MathOverflow: Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?. Question 37923 and all visible comments, checked through the Stack Exchange API on 2026-07-27. Question 37923 and all visible comments, checked through the Stack Exchange API on 2026-07-27. ↗forum · discovery source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Five-colouring triangle-free graphs of maximum degree six: UNKNOWN as of 2026-07-27. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved.Source named by the research packet.
Gholamreza Abrishami and Ahmad Erfanian, “A note on Reed's conjecture for triangle-free graphs”. Discrete Mathematics 346(12) (2023), 113609. DOI 10.1016/j.disc.2023.113609. Status evidence identified in the source record and checked at the linked publication. ↗journal article · primary source · checked 2026-08-01Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved.Also cited at Full journal article relevant to Five-colouring triangle-free graphs of maximum degree six.Source used to assess the problem's recorded status.For Five-colouring triangle-free graphs of maximum degree six: UNKNOWN as of 2026-07-27. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved.
MathOverflow: Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?, source checked for the TheoremDB status review (2026-07-31). Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:1707.07581, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved.Also cited at Full preprint relevant to Five-colouring triangle-free graphs of maximum degree six.Source used to assess the problem's recorded status.For Five-colouring triangle-free graphs of maximum degree six: UNKNOWN as of 2026-07-27. The MathOverflow page remains open with zero answers. A 2023 paper proves the claim for maximal triangle-free graphs of maximum degree below seven and verifies bounded orders, while describing the unrestricted Reed-conjecture case as unresolved.

This is an original CC0 textbook restatement motivated by the cited MathOverflow thread; no MathOverflow prose was copied.

Discussion

Loading discussion.

[#P2874] Five-colouring triangle-free graphs of maximum degree six

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance