← All problems

Faudree–Schelp–Gyárfás–Tuza conjecture on strong edge-coloring of subcubic graphs

12 years old · traced to

Let GG be a graph with maximum degree Δ(G)=3\Delta(G)=3.

Faudree–Schelp–Gyárfás–Tuza conjecture. The following bounds hold:

  1. χs′(G)≤10\chi'_s(G)\le 10.
  2. If GG is bipartite, then χs′(G)≤9\chi'_s(G)\le 9.
  3. If GG is planar, then χs′(G)≤9\chi'_s(G)\le 9.
  4. If GG is bipartite and for each edge xy∈E(G)xy\in E(G) one has d(x)+d(y)≤5d(x)+d(y)\le 5, then χs′(G)≤6\chi'_s(G)\le 6.
  5. If GG is bipartite and has no 4-cycle, then χs′(G)≤7\chi'_s(G)\le 7.
  6. If GG is bipartite and its girth is large, then χs′(G)≤5\chi'_s(G)\le 5.

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

Never refreshed

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.