The k-optimal set edge-colouring conjecture

Let GG be a graph, let kZ+k\in\mathbb{Z}^+, and let DD be a kk-optimal set, meaning a kk-dependent set maximizing ϕk(D)=kDE(G[D])\phi_k(D)=k|D|-|E(G[D])|. A subgraph is kk-edge-chromatic if its edges can be coloured with kk colours so that adjacent edges receive different colours. The kk-optimal set edge-colouring conjecture. If DD is a kk-optimal set in GG, then GG has a kk-edge-chromatic subgraph in which every vertex of V(G)DV(G)-D has degree kk.

This conjecture is introduced as a natural strengthening of the results developed earlier and is stated to imply the special case of Tuza's conjecture for graphs of the form IkHI_k\vee H. Its resolution is not supplied in the source.

Sources & referencesView supporting material

Primary source

Gregory J. Puleo, “Favaron's Theorem, k-dependence, and Tuza's Conjecture”, arXiv:1407.2336 (2015).

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.