Outerplanar graph star chromatic index conjecture

Let GG be an outerplanar graph with maximum degree Δ4\Delta\ge 4, and let χstar(G)\chi'_{\mathrm{star}}(G) denote its star chromatic index, the smallest number of colors in a proper edge coloring with no bichromatic path or cycle of length four.

Outerplanar graph star chromatic index conjecture. Every such graph satisfies

χstar(G)3Δ2+1.\chi'_{\mathrm{star}}(G)\le \left\lfloor\frac{3\Delta}{2}\right\rfloor+1.

Known bounds give χstar(G)3Δ2+12\chi'_{\mathrm{star}}(G)\le \left\lfloor\frac{3\Delta}{2}\right\rfloor+12, with the additive constant reducible to 99 by more involved analysis. The conjecture remains open.

Sources & referencesView supporting material

Primary source

Zhengke Miao, Yimin Song, Tao Wang and Xiaowei Yu, “List star edge coloring of generalized Halin graphs”, arXiv:2104.05958 (2021).

Additional references

2 papers in this index state this conjecture (2011–2021). The statement above is taken from the most recent of them; the others are arXiv:1105.1906.

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.