The tournament scheduling problem with absences

DOI10.1016/J.EJOR.2016.04.056MaRDI QIDQ323410zbMATH OpenOpenAlexFDO

Authors Uwe Schauz

Publication date 7 October 2016

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.00488

zbMATH Keywords

OR in sportsgraph coloringLatin squarescoloring gamessport scheduling

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15)

Abstract: We study time scheduling problems with allowed absences as a new kind of graph coloring problem. One may think of a sport tournament where each player (each team) is permitted a certain number $t$ of absences. We then examine how many rounds are needed to schedule the whole tournament in the worst case. This upper limit depends on $t$ and on the structure of the graph $G$ whose edges represent the games that have to be played, but also on whether or not the absences are announced before the tournament starts. Therefore, we actually have two upper limits for the number of required rounds. We have $ch{i}^t(G)$ for pre-scheduling if all absences are pre-fixed, and we have $ch{i}_{extitOL}^t(G)$ for on-line scheduling if we have to stay flexible and deal with absences when they occur. We conjecture that $ch{i}^t(G)=Delta(G)+2t$ and that $ch{i}_{extitOL}^t(G)=ch{i}^{\prime }(G)+2t.$ The first conjecture is stronger than the Total Coloring Conjecture while the second is weaker than the On-Line List Edge Coloring Conjecture. Our conjectures hold for all bipartite graphs. For complete graphs, we prove them partially. Lower and upper bounds to $ch{i}^t(G)$ and $ch{i}_{extitOL}^t(G)$ for general multigraphs $G$ are established, too.

Recommendations

• Edge coloring: a natural model for sports scheduling
• The edge-chromatic class of regular graphs of degree 4 and their complements
• Scheduling partial round robin tournaments subject to home away pattern sets
• On the multiplication of divisions: The use of graphs for sports scheduling
• Chromatic scheduling

Cites work

• scientific article; zbMATH DE number 446487 (Why is no real title available?)
• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
• Brooks' theorem via the Alon-Tarsi theorem
• Embedding Latin Squares with Prescribed Diagonal
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• Graph theory
• List edge and list total colourings of multigraphs
• Mr. Paint and Mrs. Correct
• New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs
• On embedding incomplete symmetric Latin squares
• On the application of graph colouring techniques in round-robin sports scheduling
• On the chromatic index of almost all graphs
• Proof of the list edge coloring conjecture for complete graphs of prime degree
• Round robin scheduling -- a survey
• Scheduling in sports: an annotated bibliography
• The NP-Completeness of Edge-Coloring
• The list chromatic index of a bipartite multigraph
• Total colourings of graphs

Cited in

(5)

• RobinX: a three-field classification and unified data format for round-robin sports timetabling
• Handling fairness issues in time-relaxed tournaments with availability constraints
• On the complexity of pattern feasibility problems in time-relaxed sports timetabling
• The edge-chromatic class of regular graphs of degree 4 and their complements
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants

This page was built for publication: The tournament scheduling problem with absences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q323410)