The three-colour decomposition conjecture for locally irregular graphs
The three-colour decomposition conjecture for locally irregular graphs
Let be a connected graph. A graph is locally irregular if every pair of adjacent vertices has distinct degrees. A decomposition into locally irregular subgraphs is a partition of into three sets, each inducing a locally irregular subgraph of . Let be the family of maximum-degree- graphs constructed from a triangle by repeatedly choosing a triangle with a vertex of degree 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 which does not belong to and is neither an odd-length path nor an odd-length cycle can be decomposed into 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.