We consider the dynamic graph coloring problem restricted to the class of interval graphs in the incremental and fully dynamic setting. The input consists of a sequence of intervals that are to be ...either colored, or deleted, if previously colored. For the incremental setting, we consider the well studied optimal online algorithm (KT-algorithm) for interval coloring due to Kierstead and Trotter 1. We present the following results on the dynamic interval coloring problem.■Any direct implementation of the KT-algorithm requires Ω(Δ2) time per interval in the worst case.■There exists an incremental algorithm which supports insertion of an interval in amortized O(logn+Δ) time per update and maintains a proper coloring using at most 3ω−2 colors.■There exists a fully dynamic algorithm which supports insertion of an interval in O(logn+Δlogω) update time and deletion of an interval in O(Δ2logn) update time in the worst case and maintains a proper coloring using at most 3ω−2 colors. The KT-algorithm crucially uses the maximum clique size in an induced subgraph in the neighborhood of a given vertex. We show that the problem of computing the induced subgraph among the neighbors of a given vertex has the same hardness as the online boolean matrix vector multiplication problem 2. We show that■Any algorithm that computes the induced subgraph among the neighbors of a given vertex requires at least quadratic time unless the OMv conjecture 2 is false. Finally, we obtain the following result on the OMv conjecture.■If the matrix and the vectors in the online sequence have the consecutive ones property, then the OMv conjecture 2 is false.
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
) $\theta (G)$ of a graph G $G$ is the smallest number of interval colorable graphs edge‐decomposing G $G$. We prove that θ(
G
)
=
o(
n
) $\theta (G)=o(n)$ for any graph G $G$ on n $n$ vertices. This improves the previously known bound of 2⌈n
∕
5
⌉ $2\lceil n\unicode{x02215}5\rceil $, 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 $t$ such that the graph has an interval coloring using t $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 $n$ participants can be coordinated in o(
n
) $o(n)$ no‐wait periods. In addition, we show that for any integers t $t$ and T $T$, t
<
T $t\lt 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 $t$ hours and could last T $T$ hours, but there is no possible no‐wait schedule lasting x $x$ hours if t
<
x
<
T $t\lt x\lt T$.
Interval edge-coloring: A model of curriculum scheduling Shao, Zehui; Li, Zepeng; Wang, Bo ...
AKCE international journal of graphs and combinatorics,
09/2020, Letnik:
ahead-of-print, Številka:
ahead-of-print
Journal Article
Recenzirano
Odprti dostop
Considering the appointments that teachers plan to teach some courses for specific classes, the problem is to schedule the curriculum such that the time for each teacher is consecutive. In this work, ...we propose an integer linear programming model to solve consecutive interval edge-coloring of a graph. By using the proposed method, we give the interval edge colorability of some small complete multipartite graphs. Moreover, we find some new classes of complete multipartite graphs that have interval edge-colorings and disprove a conjecture proposed by Grzesik and Khachatrian (2014).
To face the explosion of the Internet traffic, a new generation of optical networks is being developed; the Elastic Optical Networks (EONs). EONs use the optical spectrum efficiently and flexibly, ...but that gives rise to more difficulty in the resource allocation problems. In this article, we study the problem of Spectrum Assignment (SA) in Elastic Optical Tree-Networks. Given a set of traffic requests with their routing paths (unique in the case of trees) and their spectrum demand, a spectrum assignment consists in allocating to each request an interval of consecutive slots (spectrum units) such that a slot on a given link can be used by at most one request. The objective of the SA problem is to find an assignment minimizing the total number of spectrum slots to be used. We prove that SA is NP-hard in undirected stars of 3 links and in directed stars of 4 links, and show that it can be approximated within a factor of 4 in general stars. Afterwards, we use the equivalence of SA with a graph coloring problem (interval coloring) to find constant-factor approximation algorithms for SA on binary trees with special demand profiles.
A proper edge-coloring α of a graph G with colors 1,…,t is called an interval cyclict-coloring if all colors are used, and the colors of edges incident to each vertex v of G either form an interval ...of integers or the set {1,…,t}∖{α(e):eisincidenttov} is an interval of integers. A graph G is interval cyclically colorable if it has an interval cyclic t-coloring for some positive integer t. The set of all interval cyclically colorable graphs is denoted by Nc. For a graph G∈Nc, the least and the greatest values of t for which it has an interval cyclic t-coloring are denoted by wc(G) and Wc(G), respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if G is a triangle-free graph with at least two vertices and G∈Nc, then Wc(G)≤|V(G)|+Δ(G)−2. We also obtain some bounds on wc(G) and Wc(G) for various classes of graphs. Finally, we give two methods for constructing of interval cyclically non-colorable graphs.
An edge‐coloring of a graph G with colors 1,...,t is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of ...integers. In 1991, Erdős constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erdős's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204. We also consider similar problems for bipartite multigraphs.
An edge-coloring of a graph G with colors 1,…,t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. A ...graph G is interval colorable if it has an interval t-coloring for some positive integer t. In this note we prove that K1,m,n is interval colorable if and only if gcd(m+1,n+1)=1, where gcd(m+1,n+1) is the greatest common divisor of m+1 and n+1. It settles in the affirmative, a conjecture of Petrosyan.
An edge-coloring of a graph G with consecutive integers c1,…,ct is called an intervalt-coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an ...interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. The set of all interval colorable graphs is denoted by N. In 2004, Giaro and Kubale showed that if G,H∈N, then the Cartesian product of these graphs belongs to N. In the same year they formulated a similar problem for the composition of graphs as an open problem. Later, in 2009, the second author showed that if G,H∈N and H is a regular graph, then GH∈N. In this paper, we prove that if G∈N and H has an interval coloring of a special type, then GH∈N. Moreover, we show that all regular graphs, complete bipartite graphs and trees have such a special interval coloring. In particular, this implies that if G∈N and T is a tree, then GT∈N.
A proper edge-coloring of a graph G with colors 1, . . . , t is an interval t-coloring if all colors are used and the colors of edges incident to each vertex of G form an interval of integers. A ...graph G is interval colorable if it has an interval t-coloring for some positive integer t. Let
be the set of all interval colorable graphs. For a graph G ∈
, the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W(G), respectively. In this paper we first show that if G is an r-regular graph and G ∈
, then W(G⃞Pm) ≥ W(G) + W(Pm) + (m − 1)r (m ∈ N) and W(G⃞C2n) ≥ W(G) +W(C2n) + nr (n ≥ 2). Next, we investigate interval edge-colorings of grids, cylinders and tori. In particular, we prove that if G⃞H is planar and both factors have at least 3 vertices, then G⃞H
N and w(G⃞H) ≤ 6. Finally, we confirm the first author’s conjecture on the n-dimensional cube Qn and show that Qn has an interval t-coloring if and only if n ≤ t ≤
An edge-coloring of a graph G with colors 1,…,t is an intervalt-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. In ...1994, Asratian and Kamalian proved that if a connected graph G admits an interval t-coloring, then t≤(diam(G)+1)(Δ(G)−1)+1, and if G is also bipartite, then this upper bound can be improved to t≤diam(G)(Δ(G)−1)+1, where Δ(G) is the maximum degree of G and diam(G) is the diameter of G. In this note, we show that these upper bounds cannot be significantly improved.
PDF
