← All problems

Erdős’s balanced-line problem for two-colored projective planes; Kardoš’s strong edge-coloring conjecture for cubic-graph truncations

Let GG be a connected simple bridgeless cubic graph, and let T(G)T(G) be its truncation, obtained by replacing each vertex of GG with a triangle and attaching the three incident edges to distinct vertices of that triangle. If GG is not the triangular prism M0≅C3□K2M_0\cong C_3\square K_2, then χs′(T(G))=6\chi'_s(T(G))=6, where χs′(H)\chi'_s(H) denotes the minimum number of colors in a strong edge-colouring of HH. The exceptional graph satisfies χs′(T(M0))=9\chi'_s(T(M_0))=9.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

New constructions settle broad special cases, but the main coloring conjecture remains open.

The tracked issue is Kardoš’s conjecture that, apart from the triangular-prism exception, truncations of the relevant cubic bases have strong chromatic index six. The balanced-line projective-plane problem is separate and supplies no result here.

Known results

  • Six colors suffice for truncations of connected simple cubic bases that are bipartite or both bridgeless and claw-free.
  • Six colors suffice for double truncations T(T(Q))T(T(Q)) of every loopless cubic multigraph QQ.
  • The triangular-prism exception M0M_{0} has strong chromatic index 99.
  • A separate preprint reports an 1818-vertex simple diamond-free claw-free cubic graph with strong chromatic index 77; its base is a multigraph, so it does not refute the simple-base question.

Recent multigraph counterexample

Labbate and Romaniello proved the stated six-color cases. A separate preprint claims the 1818-vertex example above, refuting the broader loopless-multigraph formulation but not the exact simple-base conjecture; the claim has no independent expert assessment. The authors report that GPT-5.6 Sol Pro assisted discovery, with the result checked by hand and exact computation.

Current status (as of November 2026): Broad special cases are claimed, while the exact simple, connected, bridgeless cubic-base conjecture remains open.

Sources

Solutions 0

No solutions have been posted yet.