KIT | KIT-Bibliothek | Impressum | Datenschutz

Interval colorings of graphs—Coordinated and unstable no‐wait schedules

Axenovich, Maria 1,2; Zheng, Michael 2
1 Institut für Algebra und Geometrie (IAG), Karlsruher Institut für Technologie (KIT)
2 Fakultät für Mathematik (MATH), Karlsruher Institut für Technologie (KIT)


A proper edge‐coloring of a graph is an interval coloring if the labels on the edges incident to any vertex form an interval, that is, form a set of consecutive integers. The interval coloring thickness $θ (G)$ of a graph $G$ is the smallest number of interval colorable graphs edge‐decomposing $G$ . We prove that $θ (G) = o (n)$ for any graph $G$ on n vertices. This improves the previously known bound of $2 [n/5]$, see Asratian, Casselgren, and Petrosyan. While we do not have a single example of a graph with an interval coloring thickness strictly greater than 2, we construct bipartite graphs whose interval coloring spectrum has arbitrarily many arbitrarily large gaps. Here, an interval coloring spectrum of a graph is the set of all integers $t$ such that the graph has an interval coloring using $t$ colors. Interval colorings of bipartite graphs naturally correspond to no‐wait schedules, say for parent–teacher conferences, where a conversation between any teacher and any parent lasts the same amount of time. Our results imply that any such conference with $n$ participants can be coordinated in $o (n)$ no‐wait periods. In addition, we show that for any integers $t$ and $T,t <T$ , there is a set of pairs of parents and teachers wanting to talk to each other, such that any no‐wait schedules are unstable—they could last $t$ hours and could last $T$ hours, but there is no possible no‐wait schedule lasting $x$ hours if $t<x<T$ .

Verlagsausgabe §
DOI: 10.5445/IR/1000160671
Veröffentlicht am 17.07.2023
DOI: 10.1002/jgt.23003
Zitationen: 1
Web of Science
Zitationen: 1
Zitationen: 1
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Algebra und Geometrie (IAG)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 12.2023
Sprache Englisch
Identifikator ISSN: 0364-9024, 1097-0118
KITopen-ID: 1000160671
Erschienen in Journal of Graph Theory
Verlag John Wiley and Sons
Band 104
Heft 4
Seiten 757-768
Vorab online veröffentlicht am 05.07.2023
Schlagwörter edge-decomposition, interval coloring, no-wait, schedule
Nachgewiesen in Dimensions
Web of Science
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page