Faudree–Schelp–Gyárfás–Tuza conjecture on strong edge-coloring of subcubic graphs
Let be a graph with maximum degree .
Faudree–Schelp–Gyárfás–Tuza conjecture. The following bounds hold:
- .
- If is bipartite, then .
- If is planar, then .
- If is bipartite and for each edge one has , then .
- If is bipartite and has no 4-cycle, then .
- If is bipartite and its girth is large, then .
The conjecture concerns strong edge-colorings, in which edges at distance at most 1 receive distinct colors; equivalently, it concerns proper vertex-colorings of the square of the line graph. The source states that four parts have been confirmed, while the counterexample presented in the paper resolves the remaining conjectural claims.
References
2 papers in this index state this conjecture (2014–2021). The statement above is taken from the most recent of them; the others are arXiv:1412.8358.
Source: Daniel W. Cranston, “Strong Edge-Coloring of Cubic Bipartite Graphs: A Counterexample”, arXiv:2112.01443 (2022).
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
No solutions have been posted yet.