← All problems

Mortada–El Zein–Al Hajjar packing-colouring conjecture

For every claw-free subcubic graph GG (that is, a graph with maximum degree at most 33 and no induced subgraph isomorphic to K1,3K_{1,3}), there exists a partition V(G)=V1∪V2∪V3∪V4V(G)=V_1\cup V_2\cup V_3\cup V_4 such that, for each i∈{1,2,3,4}i\in\{1,2,3,4\} and all distinct vertices u,v∈Viu,v\in V_i, dist⁡G(u,v)>si\operatorname{dist}_G(u,v)>s_i, where (s1,s2,s3,s4)=(1,1,2,3)(s_1,s_2,s_3,s_4)=(1,1,2,3).

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A 2026 preprint claims the conjecture for claw-free subcubic graphs, while the corresponding question for all subcubic graphs remains open.

The tracked conjecture concerns packing colourings of claw-free subcubic graphs and is part of the broader question posed by Gastineau and Togni for subcubic graphs other than the Petersen graph. Mortada, El Zein, and Al Hajjar claim the claw-free case, but the supplied evidence does not establish the broader claim or any counterexamples.

Known results

  • Gastineau and Togni posed the broader (1,1,2,2)(1,1,2,2)- and (1,1,2,3)(1,1,2,3)-packing-colouring questions for subcubic graphs.
  • El Zein and Mortada (2025) proved that every non-regular subcubic graph is (1,1,2,2)(1,1,2,2)-packing colourable, while stating that a complete solution remains open.
  • Brešar, Kuenzel, and Rall proved that every claw-free cubic graph is (1,1,2,2)(1,1,2,2)-packing colourable.

2026 claw-free preprint

Mortada, El Zein, and Al Hajjar claim that every claw-free subcubic graph is (1,1,2,3)(1,1,2,3)-packing colourable, confirming the claw-free case of the Gastineau–Togni question. They also claim stronger structural and optimality results, including infinitely many claw-free subcubic graphs lacking (1,1,3,3)(1,1,3,3)- and (1,2,2,3)(1,2,2,3)-packing colourings. The preprint states that the general problem remains open; its claims are unverified.

Current status (as of October 2026): The claw-free subcubic case is claimed in an unrefereed preprint, while the broader subcubic problem remains open and no supported bridgeless-cubic disproof was found.

Sources

Solutions 0

No solutions have been posted yet.