Erdős’s balanced-line problem for two-colored projective planes; Kardoš’s strong edge-coloring conjecture for cubic-graph truncations
Let be a connected simple bridgeless cubic graph, and let be its truncation, obtained by replacing each vertex of with a triangle and attaching the three incident edges to distinct vertices of that triangle. If is not the triangular prism , then , where denotes the minimum number of colors in a strong edge-colouring of . The exceptional graph satisfies .
References
- Strong edge-colourings of truncations of cubic graphs — arXiv — Domenico Labbate, Federico Romaniello
Source: arXiv
Progress summary
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 of every loopless cubic multigraph .
- The triangular-prism exception has strong chromatic index .
- A separate preprint reports an -vertex simple diamond-free claw-free cubic graph with strong chromatic index ; 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 -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.
Solutions 0
No solutions have been posted yet.