论文标题
图形的间隔着色 - 协调和不稳定的无等待时间表
Interval colorings of graphs -- coordinated and unstable no-wait schedules
论文作者
论文摘要
如果边缘上的标签在任何顶点形成连续整数的间隔。图G的间隔厚度s（g）是最小数量的间隔可着色图边缘分解G。我们证明，对于n个顶点上的任何图G，我们证明s（g）= o（n）。这改善了Asratian，Casselgren和Petrosyan先前已知的2N/5界限。虽然我们没有一个间隔厚度的一个示例严格大于2，但我们构建了两分图的间隔频谱，其间隔频谱的任意任意较大。在这里，图的间隔频谱是所有整数t的集合，使该图具有使用T颜色的间隔着色。 两分图的间隔着色自然对应于无等待的时间表，例如父母教师会议，任何老师和任何父母之间的对话都持续相同的时间。我们的结果表明，与$ n $参与者的任何此类会议都可以在O（n）的无等待期间进行协调。此外，我们表明，对于任何整数t，t，t <t，都有一组想要互相交谈的父母和老师，因此任何没有等待的时间表都不稳定 - 他们可以持续t小时并且可以持续t小时，但是如果t <x <t <x <t <x <t <x <t，则不可能持续x小时。
A proper edge-coloring of a graph is an interval coloring if the labels on the edges incident to any vertex form an interval of consecutive integers. Interval thickness s(G) of a graph G is the smallest number of interval colorable graphs edge-decomposing G. We prove that s(G)=o(n) for any graph G on n vertices. This improves the previously known bound of 2n/5 by Asratian, Casselgren, and Petrosyan. While we do not have a single example of a graph with interval thickness strictly greater than 2, we construct bipartite graphs whose interval spectrum has arbitrarily many arbitrarily large gaps. Here, an interval 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.
