Defective Goldberg-Seymour conjecture

Let dNd\in\mathbb N^* and let GG be a graph. Define

Γd(G)=max{E(G[X])dX/2:XV(G)}.\Gamma_d(G)=\max\left\{\left\lceil \frac{|E(G[X])|}{\left\lfloor d|X|/2\right\rfloor}\right\rceil\mathrel{:}X\subseteq V(G)\right\}.

Defective Goldberg-Seymour conjecture. Every graph GG satisfies

χd(G)max{Γd(G),Δ(G)+1d}.\chi'_d(G)\leq \max\left\{\Gamma_d(G),\left\lceil \frac{\Delta(G)+1}{d}\right\rceil\right\}.

This is proposed as a generalization of the Goldberg-Seymour bound to defective edge colouring; no proof or counterexample is supplied in the source.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Guillaume Aubian and Chien-Chung Huang, “Vizing's and Shannon's Theorems for defective edge colouring”, arXiv:2201.11548 (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.