A graph G is called interval colorable if it has a proper edge coloring with colors 1, 2, 3, ... such that the colors of the edges incident to every vertex of G form an interval of integers. Not all graphs are interval colorable; in fact, quite few families have been proved to admit interval colorings. In this paper we introduce and investigate a new notion, the interval coloring thickness of a graph G, denoted theta int(G), which is the minimum number of interval colorable edge-disjoint subgraphs of G whose union is G. Our investigation is motivated by scheduling problems with compactness require-ments, in particular, problems whose solution may consist of several schedules, but where each schedule must not contain any waiting periods or idle times for all involved parties. We first prove that every connected properly 3-edge colorable graph with maximum degree 3 is interval colorable, and using this result, we deduce an upper bound on theta int(G) for general graphs G. We demonstrate that this upper bound can be improved in the case when G is bipartite, planar or complete multipartite and consider some applications in timetabling.

For a bipartite graph G with parts X and Y, an X-interval coloring is a proper edge coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by chi(int) (G, X) the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial P(Delta) such that if G has maximum degree at most A, then chi(int)(G, X) <= P(A). In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on chi(int)(G, X) for bipartite graphs with small maximum degree. (C) 2021 The Author(s). Published by Elsevier B.V.

We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring phi of the d-dimensional hypercube Q(d), we are interested in whether there is a proper d-edge coloring of Q(d) that agrees with the coloring phi on every edge that is colored under phi; or, similarly, if there is a proper d-edge coloring that disagrees with phi on every edge that is colored under phi. In particular, we prove that for any d >= 1, if phi is a partial d-edge coloring of Q(d), then phi is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or phi is proper and every color appears on at most d - 2 edges. We also show that phi is avoidable if d is divisible by 3 and every color class of phi is an induced matching. Moreover, for all 1 <= k <= d, we characterize for which configurations consisting of a partial coloring phi of d - k edges and a partial coloring psi of k edges, there is an extension of phi that avoids psi.

We consider the problem of extending and avoiding partial edge colorings of trees; that is, given a partial edge coloring phi of a tree T we are interested in whether there is a proper Delta(T )-edge coloring of T that agrees with the coloring phi on every edge that is colored under phi; or, similarly, if there is a proper Delta(T )-edge coloring that disagrees with phi on every edge that is colored under phi. We characterize which partial edge colorings with at most Delta(T ) + 1 precolored edges in a tree T are extendable, thereby proving an analogue of a result by Andersen for Latin squares. Furthermore we obtain some "mixed" results on extending a partial edge coloring subject to the condition that the extension should avoid a given partial edge coloring; in particular, for all 0 <= k <= Delta(T ), we characterize for which configurations consisting of a partial coloring phi of Delta(T ) - k edges and a partial coloring psi of k + 1 edges of a tree T, there is an extension of phi that avoids psi.

This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e. a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas.

Let F be a (possibly improper) edge-coloring of a graph G; a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with |L(v)| ≥ k for all v, and any edge-coloring F of G, G admits a coloring c adapted to F where c(v) ∈ L(v) for all v, then G is said to be adaptably k-choosable. A (k, d)-list assignment for a graph G is a map that assigns to each vertex v a list L(v) of at least k colors such that |L(x) ∩ L(y)\ ≤ d whenever x and y are adjacent. A graph is (k, d)-choosable if for every (k, d)-list assignment L there is an L-coloring of G. It has been conjectured that planar graphs are (3, l)-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably 3-choosable. Since (k, l)-choosability is a special case of adaptable k-choosablity, this implies that a planar graph satisfying these conditions is (3,1)-choosable. 

We consider the problem of extending partial edge colorings of trees. We obtain analogues of classical results on extending partial Latin squares by characterizing exactly which partial edge colorings with at most Delta(T) precolored edges of a tree T with maximum degree Delta(T) are extendable to proper Delta(T)-edge colorings of T. Furthermore, we prove sharp conditions on when it is possible to extend a partial edge coloring where the precolored edges form a matching or a collection of connected subgraphs. Finally, we consider the problem of avoiding a given (not necessarily proper) partial edge coloring.

A k-improper edge coloring of a graph G is a mapping alpha : E(G) -> N such that at most k edges of G with a common endpoint have the same color. An improper edge coloring of a graph G is called an improper interval edge coloring if the colors of the edges incident to each vertex of G form an integral interval. In this paper we introduce and investigate a new notion, the interval coloring impropriety (or just impropriety) of a graph G defined as the smallest k such that G has a k-improper interval edge coloring; we denote the smallest such k by mu(int)(G). We prove upper bounds on mu(int)(G) for general graphs G and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine mu(int)(G) exactly for G belonging to some particular classes of graphs. Furthermore, we provide several families of graphs with large impropriety; in particular, we prove that for each positive integer k, there exists a graph G with mu(int)(G) = k. Finally, for graphs with at least two vertices we prove a new upper bound on the number of colors used in an improper interval edge coloring. (C) 2021 The Author(s). Published by Elsevier B.V.

A star edge coloring of a graph is a proper edge coloring with no 2-colored path or cycle of length four. The star chromatic index chi(st)(G) of G is the minimum number t for which G has a star edge coloring with t colors. We prove upper bounds for the star chromatic index of bipartite graphs G where all vertices in one part have maximum degree 2 and all vertices in the other part has maximum degree b. Let k be an integer (k >= 1); we prove that if b = 2k + 1, then chi(st)(G) <= 3k + 2; and if b = 2k, then chi(st)(G) < 3k; both upper bounds are sharp. We also consider complete bipartite graphs; in particular we determine the star chromatic index of such graphs when one part has size at most 3, and prove upper bounds for the general case. Finally, we consider the well-known conjecture that subcubic graphs have star chromatic index at most 6; in particular we settle this conjecture for cubic Halin graphs. (C) 2021 The Authors. Published by Elsevier B.V.

Given a partial edge coloring of a complete graph K-n and lists of allowed colors for the non-colored edges of K-n, can we extend the partial edge coloring to a proper edge coloring of K-n using only colors from the lists? We prove that this question has a positive answer in the case when both the partial edge coloring and the color lists satisfy certain sparsity conditions.

We consider the problem of extending partial edge colorings of hypercubes. In particular, we obtain an analogue of the positive solution to the famous Evans conjecture on completing partial Latin squares by proving that every proper partial edge coloring of at most d-1 edges of the d-dimensional hypercube Qd can be extended to a proper d-edge coloring of Qd. Additionally, we characterize which partial edge colorings of Qd with precisely d precolored edges are extendable to proper d-edge colorings of Qd.

We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant gamma amp;gt; 0 such that if n is even and A is a 3-dimensional n x n x n array where every cell contains at most gamma n symbols, and every symbol occurs at most gamma n times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every i, j, k is an element of {1, ..., n}, the symbol in position (i, j, k) of L does not appear in the corresponding cell of A. (C) 2019 Elsevier Ltd. All rights reserved.

In this article, we discuss the Length-Constrained Cycle Partition Problem (LCCP). Besides edge weights, the undirected graph in LCCP features an individual critical weight value for each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is a feasible solution if the length of each cycle is not greater than the critical weight of each of the vertices in the cycle. The goal is to find a feasible partition with the minimum number of cycles. In this article, we discuss theoretical properties, preprocessing techniques, and two mixed-integer programming models (MIP) for LCCP both inspired by formulations for the closely related Travelling Salesperson Problem (TSP). Further, we introduce conflct hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a report on computational experiments conducted on (A)TSPLIB-based instances. As an example, we use a routing problem in which a set of uncrewed aerial vehicles (UAVs) patrols a set of areas.

In this article we introduce a Minimum Cycle Partition Problem with Length Requirements (CPLR). This generalization of the Travelling Salesman Problem (TSP) originates from routing Unmanned Aerial Vehicles (UAVs). Apart from nonnegative edge weights, CPLR has an individual critical weight value associated with each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is regarded as a feasible solution if the length of each cycle, which is the sum of the weights of its edges, is not greater than the critical weight of each of its vertices. The goal is to find a feasible partition, which minimizes the number of cycles. In this article, a heuristic algorithm is presented together with a Mixed Integer Programming (MIP) formulation of CPLR. We furthermore introduce a conflict graph, whose cliques yield valid constraints for the MIP model. Finally, we report on computational experiments conducted on TSPLIB-based test instances.

We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Qd, and lists of allowed colors for the non-colored edges of Qd, can we extend the partial coloring to a proper d-edge coloring using only colors from the lists? We prove that this question has a positive answer in the case when both the partial coloring and the color lists satisfy certain sparsity conditions. (C) 2020 Elsevier B.V. All rights reserved.

A proper edge coloring of a graph G with colors 1, 2, . . . , t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. In this paper we introduce and investigate a new notion, the cyclic deficiency of a graph G, defined as the minimum number of pendant edges whose attachment to G yields a graph admitting a cyclic interval coloring; this number can be considered as a measure of closeness of G of being cyclically interval colorable. We determine or bound the cyclic deficiency of several families of graphs. In particular, we present examples of graphs of bounded maximum degree with arbitrarily large cyclic deficiency, and graphs whose cyclic deficiency approaches the number of vertices. Finally, we conjecture that the cyclic deficiency of any graph does not exceed the number of vertices, and we present several results supporting this conjecture. (C) 2018 Elsevier B.V. All rights reserved.

We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant gamma amp;gt; 0 such that if n = 2(t) and A is a 3-dimensional n x n x n array where every cell contains at most gamma n symbols, and every symbol occurs at most gamma n times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every 1 amp;lt;= i, j, k amp;lt;= n, the symbol in position (i, j, k) of L does not appear in the corresponding cell of A.

An n x n Martial Latin square P is called dense if each row and column has at mostan non-empty cells and each symboloccurso n times in P. An x n arrayA where each cell contains subset of {1, ..., n} is a (beta n, beta n, beta n)-array if each symbol occurs at most beta n times in each row and column and each cell contains a set of size at most beta n. Combining the notions of completing partial Latin squared and avoiding arrays, we prose that there are constants alpha, beta amp;gt; 0 such that, for every positive integer n, if P is an alpha-dense n x n partial a square, A is an n x n (beta n, beta n, beta n)-array and no cell of P contains a symbol that ppears in the corresponing cell of A, then there is a completiong of P that avoids A; that is, there is a Latin square L that agrees with P on every non-empty of P, and for each i, j satisfying 1 amp;lt;= i, j, amp;lt;= n, the symbol in position (i, j) in L does not appear in the corresponding cell of A.

Given a proper edge coloring phi of a graph G, we define the palette S-G (v, phi) of a vertex v is an element of V(G) as the set of all colors appearing on edges incident with v. The palette index s(G) of G is the minimum number of distinct palettes occurring in a proper edge coloring of G. In this paper we give various upper and lower bounds on the palette index of G in terms of the vertex degrees of G, particularly for the case when G is a bipartite graph with small vertex degrees. Some of our results concern (a, b)-biregular graphs; that is, bipartite graphs where all vertices in one part have degree a and all vertices in the other part have degree b. We conjecture that if G is (a, b)-biregular, then. s(G) amp;lt;= 1 + max {a, b}, and we prove that this conjecture holds for several families of (a, b)-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.

Let G=G(n) be a graph on n vertices with maximum degree = (n). Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k-subsets of a color set C of size C sigma=sigma(n). Such a list assignment is called a random(k,C)-list assignment. In this paper, we are interested in determining the asymptotic probability (as n ) of the existence of a proper coloring phi of G, such that phi(v)L(v) for every vertex v of G, a so-called L-coloring. We give various lower bounds on sigma, in terms of n, k, and , which ensures that with probability tending to 1 as n there is an L-coloring of G. In particular, we show, for all fixed k and growing n, that if sigma(n)=(n1/k21/k) and =O(n), then the probability that G has an L-coloring tends to 1 as n. If k2 and =(n1/2), then the same conclusion holds provided that sigma=(). We also give related results for other bounds on , when k is constant or a strictly increasing function of n.

An interval t-coloring of a multigraph G is a proper edge coloring with colors 1, ... , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors. A cyclic interval t-coloring of a multigraph G is a proper edge coloring with colors 1, ... , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. Denote by w(G) (w(c)(G)) and W(G) (W-c(G)) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph G, respectively. We present some new sharp bounds on w(G) and W(G) for multigraphs G satisfying various conditions. In particular, we show that if G is a 2-connected multigraph with an interval coloring, then W(G) amp;lt;= 1 + left perpendicular vertical bar V(G)vertical bar/2 right perpendicular (Delta(G) - 1). We also give several results towards the general conjecture that W-c(G) amp;lt;= I vertical bar V(G)vertical bar for any triangle-free graph G with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most 4. (C) 2017 Elsevier B.V. All rights reserved.

A proper edge coloring of a graph G with colors 1,2,,t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree (G)4 admits a cyclic interval (G)-coloring if for every vertex v the degree dG(v) satisfies either dG(v)(G)-2 or dG(v)2. We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for (a,b)-biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)-biregular graphs as well as all (2r-2,2r)-biregular (r2) graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.

A proper edge coloring f of a graph G with colors 1, 2, 3, . . . , t is called an interval coloring if the colors on the edges incident to every vertex of G form an interval of integers. The coloring f is cyclic interval if for every vertex v of G, the colors on the edges incident to v either form an interval or the set {1, . . . t} \ {f (e) : e is incident to v} is an interval. A bipartite graph G is (a, b)-biregular if every vertex in one part has degree a and every vertex in the other part has degree b; it has been conjectured that all such graphs have interval colorings. We prove that every (3, 5)-biregular graph has a cyclic interval coloring and we give several sufficient conditions for a (3, 5)-biregular graph to admit an interval coloring. (C) 2016 Elsevier B.V. All rights reserved.

Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.

Hadwigers Conjecture states that every k-chromatic graph has a complete minor of order k. A graph G is an inflation of a graph G if G is obtained from G by replacing each vertex upsilon of G by a clique C-upsilon and joining two vertices of distinct cliques by an edge if and only if the corresponding vertices of G are adjacent. We present an algorithm for computing an upper bound on the chromatic number chi (G) of any inflation G of any 3-chromatic graph G. As a consequence, we deduce that Hadwigers Conjecture holds for any inflation of any 3-colorable graph. (C) 2015 Elsevier Ltd. All rights reserved.

Let G be a bipartite graph with bipartition (X, Y). An X-interval coloring of G is a proper edge-coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by chi(int)(G, X) the minimum k such that G has an X-interval coloring with k colors. In this paper we give various upper and lower bounds on chi(int)(G, X) in terms of the vertex degrees of G. We also determine chi(int) (G, X) exactly for some classes of bipartite graphs G. Furthermore, we present upper bounds on chi(int) (G, X) for classes of bipartite graphs G with maximum degree Delta(G) at most 9: in particular, if Delta(G) = 4, then chi(int) (G, X) amp;lt;= 6; if Delta(G) = 5, then chi(int) (G, X) amp;lt;= 15; if Delta(G) = 6, then chi(int) (G, X) amp;lt;= 33. (C) 2016 Elsevier B.V. All rights reserved.

Let G be a Class 1 graph with maximum degree 4 and let t amp;gt;= 5 be an integer. We show that any proper t-edge coloring of G can be transformed to any proper 4-edge coloring of G using only transformations on 2-colored subgraphs (so-called interchanges). This settles the smallest previously unsolved case of a well-known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5-edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7-edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent. (C) 2015 Wiley Periodicals, Inc.

A proper edge coloring of a graph with colors 1, 2, 3, ... is called an interval coloring if the colors on the edges incident to each vertex form an interval of integers. A bipartite graph is (a,b)-biregular if every vertex in one part has degree a and every vertex in the other part has degree b. It has been conjectured that all such graphs have interval colorings. We prove that all (3, 6)-biregular graphs have interval colorings and that all (3, 9)-biregular graphs having a cubic subgraph covering all vertices of degree 9 admit interval colorings. Moreover, we prove that slightly weaker versions of the conjecture hold for (3, 5)-biregular, (4, 6)-biregular, and (4, 8)-biregular graphs. All our proofs are constructive and yield polynomial time algorithms for constructing the required colorings. (C) 2014 Wiley Periodicals, Inc.

We study the complexity of finding 2-factors with various restrictions as well as edge-decompositions in (the underlying graphs of) digraphs. In particular we show that it is N P-complete to decide whether the underlying undirected graph of a digraph D has a 2-factor with cycles C-1, C-2, ..., C-k such that at least one of the cycles C-i is a directed cycle in D (while the others may violate the orientation back in D). This solves an open problem from J. Bang-Jensen et al., Vertex-disjoint directed and undirected cycles in general digraphs, JCT B 106 (2014), 1-14. Our other main result is that it is also N P-complete to decide whether a 2-edge-colored bipartite graph has two edge-disjoint perfect matchings such that one of these is monochromatic (while the other does not have to be). We also study the complexity of a number of related problems. In particular we prove that for every even k greater than= 2, the problem of deciding whether a bipartite digraph of girth k has a k-cycle-free cycle factor is N P-complete. Some of our reductions are based on connections to Latin squares and so-called avoidable arrays.

Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Delta. Assign to each vertex v of G a list L(v) of colors by choosing each list uniformly at random from all k-subsets of a color set C of size sigma(n). Such a list assignment is called a random (k,C)-list assignment. In this paper, we are interested in determining the asymptotic probability (as n -greater thaninfinity) of the existence of a proper coloring phi of G, such that phi(v)is an element of L(v) for every vertex v of G. We show, for all fixed k and growing n, that if sigma(n)=omega(n1/k2), then the probability that G has such a proper coloring tends to 1 as n -greater thaninfinity. A similar result for complete graphs is also obtained: if sigma(n)greater than= 1. 223n and L is a random (3,C)-list assignment for the complete graph K-n on n vertices, then the probability that K-n has a proper coloring with colors from the random lists tends to 1 as n -greater than infinity

We prove that there is a constant c such that, for each positive integer k, every (2k + 1) x (2k + 1) array A on the symbols 1, ... , 2k + 1 with at most c(2k + 1) symbols in every cell, and each symbol repeated at most c(2k + 1) times in every row and column is avoidable; that is, there is a (2k + 1) x (2k + 1) Latin square S on the symbols 1, ... , 2k + 1 such that, for each i, j is an element of {1, ... , 2k + 1}, the symbol in position (i, j) of S does not appear in the corresponding cell in Lambda. This settles the last open case of a conjecture by Haggkvist. Using this result, we also show that there is a constant rho, such that, for any positive integer n, if each cell in an n x n array B is assigned a set of m andlt;= rho n symbols, where each set is chosen independently and uniformly at random from {1, ... , n}, then the probability that B is avoidable tends to 1 as n -andgt; infinity.

Let P be an n×n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbol s. Assume further that s is the symbol of cell (r,c) in P. We prove that P is completable to a Latin square if n≥8 and n is divisible by 4, or n≤7 and n∉{3,4,5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square.