The three-colour decomposition conjecture for locally irregular graphs

Let GG be a connected graph. A graph is locally irregular if every pair of adjacent vertices has distinct degrees. A decomposition into 33 locally irregular subgraphs is a partition of E(G)E(G) into three sets, each inducing a locally irregular subgraph of GG. Let T\mathfrak{T} be the family of maximum-degree-33 graphs constructed from a triangle by repeatedly choosing a triangle with a vertex of degree 22 and appending either a hanging path of even length or a hanging path of odd length with a triangle attached at its other end.

Three-colour decomposition conjecture. Every connected graph GG which does not belong to T\mathfrak{T} and is neither an odd-length path nor an odd-length cycle can be decomposed into 33 locally irregular subgraphs.

The excluded graphs were subsequently shown to be exactly the connected graphs that admit no decomposition into any number of locally irregular subgraphs, so this conjecture is solved.

Sources & referencesView supporting material

Primary source

Jakub Przybyło, “On decomposing graphs of large minimum degree into locally irregular subgraphs”, arXiv:1508.01129 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.