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

- ID: `P2874`
- Reference: `triangle-free-degree-six-five-colouring`
- Page: https://theoremdb.org/statements/P2874
- Record maturity: Reviewed problem with recorded work

## Problem

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

### Definitions

- **Definition.** A graph is triangle-free when it has no three vertices that are pairwise adjacent.
- **Definition.** A proper five-colouring is a map from the vertex set to a set of five colours such that adjacent vertices receive different colours.

### What 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.

## 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. 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](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

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.

- Original intake status: 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.
- 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: 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.

### Open directions

- **Route 1** (reported): 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](#reference-1)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `triangle-free-degree-six-five-colouring`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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. https://mathoverflow.net/questions/37923/does-every-triangle-free-graph-with-maximum-degree-at-most-6-have-a-5-colouring
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - forum; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.
2. <a id="reference-2"></a>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. Full journal article relevant to Five-colouring triangle-free graphs of maximum degree six. https://doi.org/10.1016/j.disc.2023.113609
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - 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.
3. <a id="reference-3"></a>Jan Goedgebeur, “On minimal triangle-free 6-chromatic graphs”. arXiv:1707.07581 (2017). Full preprint relevant to Five-colouring triangle-free graphs of maximum degree six. https://arxiv.org/abs/1707.07581
   - preprint; reference source; arXiv:1707.07581, checked 2026-07-31; checked 2026-07-31
   - Source use: citation_only
   - 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.