The inclusion chromatic index bound for connected graphs

About 7 years old · traced to

Let GG be a connected graph with minimum degree δ≥2\delta\geq 2 and maximum degree Δ\Delta, and let χ⊂′(G)\chi'_{\subset}(G) denote its inclusion chromatic index, the least number of colours in a proper edge colouring such that the palette at every vertex is not contained in the palette at any neighbour. Inclusion chromatic index conjecture. If GG is not isomorphic to C5C_5, then

χ⊂′(G)≤⌈(1+1δ−1)Δ⌉.\chi'_{\subset}(G) \leq \left\lceil\left(1+\frac{1}{\delta-1}\right)\Delta\right\rceil.

The conjectured bound matches the lower bound supplied by the paper's infinite family of examples and would therefore be sharp. The paper proves an upper bound with an additive constant for every fixed δ≥2\delta\geq 2, with 1δ−1\frac{1}{\delta-1} replaced by 4δ−1\frac{4}{\delta-1}; the stated bound remains open.

References

Primary source

Jakub Kwaśny and Jakub Przybyło, “On inclusion chromatic index of a graph”, arXiv:1909.00150 (2019).

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.