The tournament scheduling conjecture for on-line scheduling

Let GG be a non-edgeless multigraph, let tNt\in\mathbb{N}, and let χOLt(G)\chi_{\textit{OL}}^t(G) denote the worst-case number of rounds required for on-line scheduling when each vertex is allowed tt absences. Let χ(G)\chi'(G) be the chromatic index of GG. On-line scheduling conjecture. For every such GG and tt,

χOLt(G)=χ(G)+2t.\chi_{\textit{OL}}^t(G)=\chi'(G)+2t.

This is described as a weakening of the on-line List Edge Coloring Conjecture and would determine the on-line scheduling number for all non-edgeless multigraphs once the chromatic index is known. The source gives no resolution; it notes that the equality is known in several special cases.

Sources & referencesView supporting material

Primary source

Uwe Schauz, “The Tournament Scheduling Problem with Absences”, arXiv:1509.00488 (2016).

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.