Four-colour conjecture for generalized total colourings of planar graphs

Every finite planar graph $G$ admits a colouring $c:V(G)\cup E(G)\to\{1,2,3,4\}$ such that: (i) any two adjacent vertices, adjacent edges, or incident vertex-edge pairs receive distinct colours; (ii) for each colour $i\in\{1,2,3,4\}$ , the induced subgraph $G[\{v\in V(G):c(v)=i\}]$ is a forest; and (iii) for each colour $i\in\{1,2,3,4\}$ , the edge subgraph $(V(G),\{e\in E(G):c(e)=i\})$ is a forest.

Progress summary

Partially solved

The conjecture is confirmed for two broad families of planar graphs, but it remains unproved for planar graphs in general.

The problem concerns a four-colour bound for generalized total colourings of planar graphs, conjectured in 2016. The full planar-graph statement remains open.

August 2026 structured-family result

Philippe Cara and Samantha Dorfling proved the conjectured bound for two infinite families of planar graphs. This is genuine partial progress, not a proof of the general conjecture.

Current status (as of August 2026): the conjectured bound is proved for two infinite planar-graph families, while the general planar-graph conjecture remains unresolved.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

arXiv

Additional references

On Generalized Total Colourings of Planar Graphs — arXiv — Cara, Philippe, Dorfling, Samantha

3 hours ago