New results on the robust coloring problem

Results Math (2024) 79:122 Online First c 2024 The Author(s) https://doi.org/10.1007/s00025-024-02148-w Results in Mathematics New Results on the Robust Coloring Problem Delia Garijo , Alberto M´arquez, and Rafael Robles Abstract. Many variations of the classical graph coloring model have been intensively studied due to their multiple applications; scheduling problems and aircraft assignments, for instance, motivate the robust coloring problem. This model gets to capture natural constraints of those optimization problems by combining the information provided by two colorings: a vertex coloring of a graph and the induced edge coloring on a subgraph of its complement; the goal is to minimize, among all proper colorings of the graph for a fixed number of colors, the number of edges in the subgraph with the endpoints of the same color. The study of the robust coloring model has been focused on the search for heuristics due to its NP-hard character when using at least three colors, but little progress has been made in other directions. We present a new approach on the problem obtaining the first collection of non-heuristic results for general graphs; among them, we prove that robust coloring is the model that better approaches the equitable partition of the vertex set, even when the graph does not admit a so-called equitable coloring. We also show the NP-completeness of its decision problem for the unsolved case of two colors, obtain bounds on the associated robust coloring parameter, and solve a conjecture on paths that illustrates the complexity of studying this coloring model. Mathematics Subject Classification. 68R10, 05C15. Keywords. Graph theory, discrete optimization, graph coloring, robust coloring. 1. Introduction Coloring problems deal with partitioning the objects of a graph into classes according to different criteria, and appear in many areas with seemingly no 0123456789().: V,-vol 122 Page 2 of 20 D. Garijo et al. Results Math connection with coloring: time tabling and scheduling [3], frequency assignment [17], register allocation [4], printed circuit board testing [10], pattern matching [15] or analysis of biological and archeological data [2]; see also [16] for descriptions of the first four mentioned applications. The classical coloring problem uses proper colorings: a k-proper coloring is an assignment of kcolors to the vertices of a graph so that no edge has both endpoints of the same color. This is an NP-hard problem for three or more colors (and polynomial for two colors), which has received a large attention in the literature, not only for its real world applications, but also for its theoretical aspects and computational difficulty; see, for instance [5,9]. Other different criteria have been considered in coloring problems as the equitable partition, that is, partitioning the vertex set of a graph into equal or almost equal subsets. Formally, a graph is equitable k-colorable if it admits a k-proper coloring such that the cardinalities of any two color classes differ by at most one. Equitable coloring of graphs was introduced by Meyer [14] for modeling problems in an operations research context, and has since been widely investigated due to its many practical applications in sequencing and scheduling; see for example [8] and the references therein, in particular, [7] for a specific application in scheduling. As explained in [8], this type of coloring models situations in which one desires to split a system into equal or almost equal conflict-free subsystems. However, not every system admits such a division, and other criteria are needed in order to approach as much as possible the equitable partition; here arises the robust coloring problem (RCP, for short) that can be stated as follows: Let G=(V(G),E(G)) be an unweighted and simple graph with chromatic number χ(G). Given a subgraph Hof its complement graph Gand a positive integer k≥χ(G), find a k-proper coloring φ of Gthat minimizes, over all those k-proper colorings, the number of monochromatic edges1in the induced coloring on H. We say that φis a k-robust coloring of (G, H), and m(G, H, k) is such minimum. The original statement of the problem introduced in [19] considers Hto be a weighted graph, and the goal is to minimize the sum of the weights of the monochromatic edges. Our statement establishes all edge weights in Hto be 1, as both versions are equivalent for most of the questions addressed in this work, and for those that are not, our arguments can be adapted. We will be more precise on this issue in each of the sections below, once the different problems that we approach have been described in detail. Applications of robust coloring are summarized in [12,19]; among them, it highlights applications to timetabling and scheduling problems, geographical maps, and aircraft assignment. For example, the aircraft assignment problem 1Monochromatic edges are those whose endpoints have the same color; otherwise the edges are called bichromatic. New Results on the Robust Coloring Problem Page 3 of 20 122 can be modeled as a graph coloring problem where each vertex in the graph Grepresents a flight route and each color represents one aircraft. There is an edge between two vertices if an aircraft cannot serve the two flight routes represented by the two vertices. If flight-delays are taken into account, the overlap relationship between flight routes changes, and this information is captured by the edges of a new graph H. The monochromatic edges in Hrepresent cancelled flights, and the goal is to minimize the number of flights that must be cancelled when there are kaircrafts. Related work. As it was mentioned before, the RCP was introduced in [19], where the authors also describe several applications of this coloring model, and conclude that the decision problem is NP-complete for k≥3. They also present a binary programming model and outline a genetic algorithm. Due to their complexity result, most papers in the topic search for heuristics. In [18] the authors develop several meta-heuristics to solve the RCP including genetic algorithm, simulated annealing and tabu search. A column generationbased heuristic algorithm is presented in [20]. A study on the robust aircraft assignment is developed in [12]; the authors propose new techniques for an approximate solution of the problem, such as the partition based encoding and several meta-heuristics (local search, simulated annealing, tabu search and hybrid method). Other references in this direction are [1,6]. Almost no progress has been made in other directions: we can only refer the reader to [13] for a theoretical study on the RCP for the case of Gand Hbeing paths on the same set of vertices and the value k= 3. The authors present an exact but exponential algorithm to find a 3-robust coloring of (G, H), and a randomized algorithm and a greedy algorithm analyzing the cost of their output. They also apply their randomized algorithm to obtain bounds on the problem of maximizing the sum of the weights (costs) of the monochromatic edges of H, and pose two conjectures related with bounding the number of monochromatic edges of Hinduced by a 3-coloring of G. Our results. We present a non-heuristic approach to the RCP for general graphs. In Sect. 2, we first prove that robust coloring is the model that better approaches the equitable partition even when the graph has no equitable coloring; if the graph admits such a coloring, we extend the known connection between robust colorings of (G, G) and equitable colorings of Gto a broad class of subgraphs H. The NP-complete nature of the decision problem of robust coloring is then established in Sect. 2.1 for the unsolved case of two colors, in contrast to the corresponding decision problems for classical graph coloring and equitable coloring. Section 2.2 focuses on the modifications required by the greedy algorithm for classical graph coloring in order to guarantee an optimal solution (for some vertex ordering) when dealing with robust colorings and equitable colorings. We introduce the robust-greedy algorithm as the variation satisfying that property. This algorithm is key in Sect. 3, where we first obtain a tight upper bound on m(G, H, k) for arbitrary graphs Gand subgraphs H, 122 Page 4 of 20 D. Garijo et al. Results Math a b c d e f a b d e f a d e f a b c d e f K3,3K3,3=K3,3[S]K3,3[S] S={a, b, d, e, f} K3,3[S] S ={a, d, e, f} S=V(K3,3) Figure 1. A 3-coloring of K3,3, and the induced edge colorings in K3,3,K3,3[S], and K3,3[S]; the sets Sand S admit an equitable 3-coloring, and Sdoes not and then for graphs defined as α-greedy orientable (this includes trees, some series–parallel graphs and bipartite outerplanar graphs). In Sect. 4,weprove in the affirmative a conjecture posed by L´opez-Bracho et al. [13]onm(G, H, 3) for Gand Hbeing two paths on the same set of vertices, and extend the result to Hbeing a vertex-disjoint union of paths; the solution of this conjecture illustrates very well the complexity of dealing with robust colorings. We assume k<min{|V(G)|,χ(G)χ(H)}for otherwise m(G, H, k)=0as there are always enough colors to obtain a proper coloring in Gand also in H. In addition, for short, we omit the term proper and simply say coloring when no confusion may arise. 2. Robust Colorings as an Approach to Equitable Colorings When a graph Ghas an equitable coloring, one obtains a uniform distribution of colors on the vertices, and the question is whether this decreases the number of monochromatic edges in a subgraph Hof G, but this question can not be answered for an arbitrary Has the answer would completely depend on its structure. Thus, it makes sense to study the connection between equitable colorings and robust colorings when His the whole G. In this section, we go further by setting Has the induced subgraph in Gby a subset of vertices S⊆V(G). We denote this graph as G[S], see Fig. 1for some examples. For graphs Gthat admit an equitable coloring, it is known that a kcoloring of Gis equitable if and only if it is a k-robust coloring of (G, G); this can be deduced, for instance, from [19, Proposition 3.1]. We first prove that, even if Gdoes not admit an equitable coloring, robust coloring is the model that better approaches the uniform distribution of colors. Let S⊆V(G), and consider the color classes C1,...,C kthat partition V(G)byak-coloring φof G(each class contains the vertices with the corresponding color). Let Pφ,S =(n1,...,n k) be the partition of |S|associated to the coloring φ, where ni=|Ci∩S|. We say that φis equitable over Sif Pφ,S satisfies that |ni−nj|≤1for1≤i, j ≤k; with some abuse of the language, we may indistinctly say that Sadmits an equitable k-coloring (see Fig. 1). There New Results on the Robust Coloring Problem Page 5 of 20 122 are monochromatic edges in the induced edge coloring of G[S] if and only if ni>1 for some 1 ≤i≤k; each pair of vertices of Sin the same color class Ci determines a monochromatic edge, and so the total number of monochromatic edges induced by the partition Pφ,S in G[S], denoted by m(Pφ,S), is m(Pφ,S)=  1≤i≤k,ni>1ni 2,(1) which can be rewritten as m(Pφ,S)=1 2 k  i=1 (n2 i−ni)=1 2 k  i=1 ni−1 22 −1 4=−k 8+1 2d2(Pφ,S,Q), where d(Pφ,S,Q) is the Euclidean distance between the point Pφ,S=(n1,...,n k) and the point Q=( 1 2,...,1 2)inak-dimensional space. (Note that, in the above equation, we include in the sum the case ni= 1 since n2 i−ni= 0.) We can thus conclude that m(Pφ,S) is mimimum over all k-colorings φ of Gif and only if d(Pφ,S ,Q) is minimum. Hence, minimizing the number of monochromatic edges in the induced coloring of G[S] is equivalent to finding the point Pφ,S in the hyperplane described by the equation n1+n2+...+ nk=|S|that minimizes the distance to Q. Further, d(Pφ,S ,Q) is minimum if and only if d(Pφ,S ,P |S|,k) is minimum, where P|S|,k =( |S| k,...,|S| k)isthe orthogonal projection of Qonto that hyperplane. Observe that P|S|,k represents the ideal uniform distribution into the kcolor classes. This distribution may not exist (|S|might not even be divisible by k) but we have shown that the k-robust coloring is the closest to it under the Euclidean metric; this is the content of the following theorem. Theorem 2.1. Ak-coloring φof a graph Gis a k-robust coloring of (G, G[S]) if and only if d(Pφ,P |S|,k)is minimum over all k-colorings of G. Consider now a k-robust coloring φof (G, G[S]) and the partition Pφ,S = (n1,...,n k). Suppose that ni<n jfor some 1 ≤i, j ≤k, and let P= (n1,...,n i+1,...,n j−1,...n k); this is a k-partition of |S|that is not necessarily associated to a k-coloring but, with some abuse of notation, we set m(P)as m(P)=ni+1 2+nj−1 2+ =i,j n 2. By Eq. (1), we have m(Pφ,S )−m(P)=nj−ni−1≥0, and so m(Pφ,S )≥m(P). Therefore, any partition of |S|satisfying that any two of its elements differ by at most one is a minimum of the function m(·) over all k-partitions of |S|. Thus, we have proved the following proposition, where we also give the minimum value of the function m(·), which is straightforward. 122 Page 6 of 20 D. Garijo et al. Results Math Proposition 2.1. For every k≥χ(G)it holds that: m(G, G[S],k)≥(k−r)s 2+rs+1 2, where s=|S| kand r=|S|−sk. Moreover, the bound is tight if and only if Sadmits an equitable k-coloring. The preceding lower bound is the number of monochromatic edges in the induced edge coloring of G[S] by an equitable k-coloring over S, if it exists. Thus, we extend the known connection between equitable colorings and robust coloring to the graph G[S]. Theorem 2.2. Let S⊆V(G)be a subset of vertices that admits an equitable k-coloring. Then, a k-coloring φof Gis equitable over Sif and only if φis a k-robust coloring of (G, G[S]). We next illustrate the previous results with some examples. Example 2.1. Figure 2shows a 4-equitable coloring of a graph G, which by the relation between equitable colorings and robust colorings, is a 4-robust coloring of (G, G). The problem arises when a graph has no equitable coloring for some value k. This happens to the complete bipartite graph K3,3when setting k=3 since any 3-coloring generates color classes C1,C 2,C 3of cardinality 1,2,3, respectively. See Fig. 1. Theorem 2.1 establishes that the closest partition of the vertex set to an equitable partition is given by a 3-robust coloring of (G, G). Further, Theorem 2.2 allows us to study the scenario for subsets Sof vertices in K3,3. All subsets Scontaining at most two vertices of class C3admit an equitable 3-coloring. Moreover, m(G, G[S],3) is either 1 or 2 (depending on the set Sconsidered). Example 2.2. The argument to prove Proposition 2.1 can be used to obtain robust colorings of (G, G[S]) when the graph Gdoes not admit equitable colorings. For instance, the wheel graph W1,7with 8 vertices has no equitable colorings as there is always a color class of cardinality 1 (determined by the central vertex). For k= 4, the above mentioned argument establishes that the partition (1,1,3,3) can not be associated to a 4-coloring of W1,7that is a 4-robust coloring of (W1,7, W1,7), but (1,2,2,3) gives such a robust coloring. 2.1. Complexity of Robust Colorings The classical graph coloring decision problem is NP-complete for k≥3 colors, but polynomial for k=2[9]. The same happens for equitable k-coloring [8]. Now, consider the following problem: Robust-Coloring Instance: AgraphG, a subgraph Hof G, a positive integer k≤|V(G)|,and m∈N. New Results on the Robust Coloring Problem Page 7 of 20 122 Figure 2. AgraphGthat admits 4-equitable colorings (as the one shown), which are 4-robust colorings of (G, G). None of them can be obtained by the greedy algorithm with any of the 8! possible vertex orderings Question: Does a k-coloring of Gexist such that the number of monochromatic edges in the induced coloring on His at most m? A reduction to graph coloring shows the NP-completeness of Robust-Coloring for k≥3[19, Proposition 3.2]. We next prove that, surprisingly, this decision problem is NP-complete even for k=2. Theorem 2.3. Robust-Coloring is an NP-complete problem for k=2. Proof. The problem is in NP since one can compute in polynomial time the number of monochromatic edges induced in Hby a given k-coloring of G, and check whether this number is at most m. Consider now the following NP-complete problem [11]: Simple-Max-Cut Instance: AgraphG=(V,E), ∈N. Question: Does there exist a set S⊂Vsuch that |{su ∈E|s∈S, u ∈ V−S}| ≥ ? We next reduce Simple-Max-Cut to our decision problem, thus proving the result. Let G=(V,E) be a graph with nvertices, and let ∈N.LetVnbe the trivial graph with nvertices (i.e., it has no edges); the graph Gis a subgraph of Vn. Any 2-coloring of Vninduces a partition of Vinto two subsets Sand V−S such that the bichromatic edges in the induced coloring on Gare precisely the set {su ∈E|s∈S, u ∈V−S}. Therefore, |{su ∈E|s∈S, u ∈V−S}| ≥ ⇐⇒ m(Vn,G,2) ≤|E|−. The inequation m(Vn,G,2) ≤|E|−is equivalent to the existence of a 2- coloring of Vnsuch that the number of monochromatic edges in the induced coloring on Gis at most |E|−. 2.2. Robust-Greedy Algorithm For classical graph coloring, it is well-known that there always exists a vertex ordering in any graph such that the greedy algorithm2gives an optimal proper 2Recall that the greedy algorithm for graph coloring considers an ordering of the vertices of the graph and assigns to each vertex its first available color (i.e., the first color that has not been assigned to any of its already colored neighbours). 122 Page 8 of 20 D. Garijo et al. Results Math coloring, that is, a proper coloring using the minimum number of colors. However, this is not true for robust coloring, and neither for equitable coloring as the example in Fig. 2shows. We next introduce a variation of the greedy algorithm, called the robust-greedy algorithm, which captures the constraints of the robust colorings and gives, for some ordering of the vertices of any graph, the closest partition to the equitable partition. Further, this algorithm will lead, together with the notion of α-greedy orientable graph (introduced in Sect. 3.1), to upper bounds on m(G, H, k) for well-known families of graphs G and arbitrary subgraphs Hof G. As the classical greedy algorithm for graph coloring, the robust-greedy algorithm also processes the vertices of a graph Gin a given ordering, and there is an ordered list of colors (they are simply taken in order). In addition, we must keep track of the number of monochromatic edges on a fixed subgraph Hof G. Robust-greedy algorithm Each vertex vof Gis given the first color cof the list satisfying the two following properties: (a) color cis available for v, i.e., it has not been assigned to the already colored neighbours of vin G; (b) it minimizes, among all available colors for v, the number of monochromatic edges on Hwith vas an endpoint. The algorithm stops when all vertices of Ghave been colored. As we pointed out before, some questions on robust coloring cannot be approached for general subgraphs Hof Gsince the answer would depend on the structure of H, and it makes then sense to set H=G. This happens in the following theorem. Theorem 2.4. Let Gbe a graph, and let k≥χ(G)be a positive integer. There always exists a vertex ordering of Gsuch that the robust-greedy algorithm provides a k-robust coloring of (G, G). Proof. Let φbe a k-robust coloring of (G, G), and consider the color classes Ci={ui 1,...,u i ni},1≤i≤k,inwhichφpartitions V(G). Assume that the classes are ordered by increasing cardinality: ni≤njfor 1 ≤i<j≤k. Let Obe a vertex ordering obtained by choosing a vertex from each class Ciin a cyclic way (in increasing order) until there are no vertices left in any of the classes, for example, Ocould be: u1 1,u 2 1,...,u k 1,u 1 2,u 2 2,...,u k 2,...,u 1 n1,..., uk n1,u 2 n1+1,...,u k n1+1,...,u k nk. The robust-greedy algorithm assigns color 1 to u1 1(the same first color as φ), and when it processes u2 1it may happen that: (i) u1 1u2 1∈E(G)and so u2 1would be assigned color 2 by condition (a) of the algorithm, or (ii) u1 1u2 1∈E(G) and so, by condition (b) of the algorithm, u2 1would also be assigned color 2 (this color minimizes, among colors 1 and 2, the number of monochromatic edges in Gwith u2 1as endpoint). Hence, the robust-greedy New Results on the Robust Coloring Problem Page 9 of 20 122 algorithm assigns the same colors as φto u1 1and u2 1. This argument can be extended to the first kn1vertices, to which the algorithm assigns the same colors as φgenerating kcolor classes with the same size n1(after processing the vertices u1 1,u 2 1,...,u k 1,...,u 1 n1,...,u k n1of the ordering O). Now, the algorithm could assign the same colors as φto the remaining vertices but, if at some later stage, the robust-greedy algorithm assigns to a vertex a different color than that assigned by φ, we stop the algorithm and color the remaining vertices with the same colors as φ, obtaining a new k-coloring ψ. The associated partitions Pφ,V (G)and Pψ,V (G)only differ in one element: roughly speaking, one vertex has changed from a bigger color class to a smaller one. Following the same argument as for Proposition 2.1, we obtain that m(Pφ,V (G))≥m(Pψ,V (G)). Since φis a robust coloring then m(Pφ,V (G))=m(Pψ,V (G)). For each change of color produced by the robustgreedy algorithm, we can argue as above obtaining a sequence of k-robust colorings of (G, G) that lead to the desired k-robust coloring generated by the algorithm.  The analogous of Theorem 2.4 for equitable partitions of vertex sets is obtained from Theorem 2.2 by setting S=V(G). Corollary 2.1. For every equitable k-colorable graph G, there always exists a vertex ordering such that the robust-greedy algorithm provides an equitable kcoloring of its vertices. 3. Upper Bounds on m(G, H, k)for Arbitrary H In this section we deal with arbitrary subgraphs Hof G.3We first present a tight upper bound on m(G, H, k) for every graph G, for which we need the following technical lemma, where two distinct colorings are considered, one of them not necessarily proper. Thus, to avoid any confusion, the term proper will not be omitted in Lemma 3.1 and Theorem 3.1. Lemma 3.1. Let t≥2. For every proper t-coloring of a graph Gand every positive integer t∈[1,t]there exists a t-coloring of Gthat induces at most |E(G)|·2(t−t) ttmonochromatic edges in G. Proof. The result is straightforward for t=1as|E(G)|is the number of monochromatic edges induced by any 1-coloring of Gand 2(t−1) t≥1fort≥2. If t=tthe result establishes that there are no induced monochromatic edges, which is true for any proper t-coloring of G. Assume now that 1 <t <t, and let φbe a proper t-coloring of G,which induces an edge coloring of G(according to the colors of the endpoints of the 3Our results consider Hto be unweighted but our arguments can be easily adapted for multigraphs and graphs with rational edge weights; in the case of real edge weights, we can approximate them (using rational weights) with the desired precision. 122 Page 16 of 20 D. Garijo et al. Results Math Suppose now that s=0.Let{u1,...,u n}be the set of vertices of the path G(viewed as an horizontal path) ordered from left to right. We distinguish three cases. Case 1:There is a vertex ui,i=n,satisfying that there exists a unique edge ujukin Hsuch that j<iand k>i(one endpoint of the edge is to the left and the other to the right of ui). We proceed by induction on n.Let G1and G2be, respectively, the sub-paths of Gon vertices {u1,...,u i}and {ui+1,...,u n},thatis,G=G1∪G2∪{uiui+1}. Similarly, we consider the graph H=H1∪H2∪{ujuk}, where Hiis the subgraph of Hcontained in Gi.Every 3-robust coloring of (G, H) can be modified to make the edge ujukbichromatic: it suffices to maintain the coloring of G1and change the color of ukwith other color in G2, if needed. Thus, m(G, H, 3) = m(G1,H 1,3) + m(G2,H 2,3), and by induction the result follows. Case 2: Vertex unhas degree three in G∪H. Again, we use induction on n. Let e1,e 2be the two edges of Hincident with un. Starting from un−1,from right to left, consider the two first right endpoints uk,u j,j≤k, of edges in H; the corresponding edges are denoted, respectively, by e3and e4.LetG1 be the sub-path of Gon vertices {u1,...,u j}, and let H1⊂G1be either H\{ei|1≤i≤3}(if uk=uj)orH\{ei|1≤i≤2}(if uk=uj). The difference between a 3-robust coloring of (G, H)andoneof(G1,H 1) relies on at most one edge more that can be monochromatic. Indeed, once the vertices of G1have been colored, we color the vertices from unto uj+1: there is one available color for unto make e1and e2bichromatic, and the induced coloring on e4always comes from the coloring in G1.Thus,e3would be the unique edge that could increase the number of monochromatic edges when uk=uj. Hence, m(G, H, 3) ≤m(G1,H 1,3) + 1, and the desired bound is obtained by induction. Case 3: The pair (G, H)satisfies neither case 1 nor case 2.Wepresentavertex coloring procedure in which we first go from left to right assigning colors to the vertices so that as long as possible no monochromatic edge is generated in G∪H. If we can color all the vertices, then m(G, H, 3) = 0; otherwise a saturated vertex ui,3<i<n, is found: a vertex is saturated if its degree in G∪His four and, when it is first visited, three of its neighbours have already been colored with the three available colors. In this case, vertex uiis not assigned a color, and we continue visiting vertices without coloring until the first conditioned vertex ujis found: a non-colored vertex (at some stage) ujis conditioned if it is an endpoint of an edge of Hwhose other endpoint uthas already been colored (t<i); the edge utujis said to be semi-colored. Observe that at this stage vertices from u1to ui−1are colored, and those from uito unare not (including uj). Note also that vertex ujmust exist as s=0 and ui=un. As an example, in Fig. 7, vertex uiis saturated and vertices uj and ukare conditioned. We next describe how our procedure obtains a proper coloring of Gwith the property that the total number of monochromatic edges in Hequals the New Results on the Robust Coloring Problem Page 17 of 20 122 number of saturated vertices found during the process. More concretely, when a saturated vertex is visited, there are four or five edges of Hinvolved of which only one has to be monochromatic. If vertex ujhas two semi-colored edges e1and e2, we first assign a color to ujto make both edges bichromatic. Then, vertices from uj−1to uiare colored (from right to left) to maintain the proper coloring in G; this gives one monochromatic edge among the two edges of Hincident with ui. Assume now that ujhas a unique semi-colored edge e1, and let ukbe the first (from left to right) conditioned vertex in {uj+1,...,u n}; this vertex must exist since otherwise e1would be the unique edge with one endpoint to the left and the other to the right of ui(case 1). If ukhas two semi-colored edges e2and e3(see Fig. 7a), we first color ukand ujso that edges ei,1≤i≤3 are bichromatic. Then, from right to left, vertices {uk−1,...u j+1}and {uj−1,...u i}can be properly colored. Finally, suppose that vertex ukhas a unique semi-colored edge e2. (i) If ujhas either degree 3 in G∪Hor an incident edge e3with the other endpoint ubetween uiand uj(i<<j), we first visit, from right to left, vertices {uk,...,u j}assigning colors to make e1and e2bichromatic. Then we color, again from right to left, {uj−1,...,u i}so that e3(if it exists) is bichromatic; this is possible since we are coloring from right to left so, when uis visited, there are two available colors. Refer to Fig. 7b. (ii) If ujhas an incident edge e3with the other endpoint ubetween ujand uk(j<<k), we randomly assign to ukone of the two colors that make e2bichromatic, and proceed to color from right to left vertices {uk−1,...,u j} using only the color of ukand that of the other endpoint of e2. Our aim is that e1and e3are bichromatic, but it may happen that, with our assignment, they can not be both bichromatic while maintaining the proper coloring in G; this happens for example giving color 1 to ukin Fig. 7c. In this case, we change the color of all vertices in {uk,...,u j+1}that have the same color as ukby the other color that preserves e2as bichromatic (in our example, we would change color 1 by color 3). Then, we color vertices from uj−1to ui. We thus conclude that, when a saturated vertex is visited, our procedure generates one monochromatic edge in H, and at least three bichromatic ones. Hence, m(G, H, 3) ≤|E(H)| 4. Figure 6illustrates examples for s=0and s>0 where the bound is tight.  5. Concluding Remarks In this work we have presented the first non-heuristic study for general graphs on the robust coloring model. We delved into the connection beetween robust colorings and equitable colorings, encompassing a complexity study. We also obtained the first general bounds on the parameter m(G, H, k), and solved an intriguing conjecture on paths. These are important steps on this difficult 122 Page 18 of 20 D. Garijo et al. Results Math uiuj e1e2 32 11212 3 uk (a) e3 uiuj e1e2 32 11212 3 uk (b) e3 u uiuj e1e2 32 11212 3 uk (c) e3 u Figure 7. Edges of Gin black, and edges of Hin red; vertices {u1,...,u i−1}have already been colored (colors 1–3). Vertex ukhas two semi-colored edges in (a)andonein(b) and (c); the difference between these two cases is the position of the endpoint uof e3 and challenging problem that leave different types of open questions for future research: •The problem of deciding whether a general graph has an equitable kcoloring with a given number of colors k≥3 is NP-complete [8]. However, it would be interesting to find a broad class of graphs for which a polynomial time algorithm could be designed. The algorithm could also be applied to robust coloring by means of Theorem 2.2. •In order to improve the upper bounds of Sect. 3, we think that new techniques must be developed, rather than trying to enhance them by using a similar approach to the one presented in this paper. •The proof of Theorem 4.1 shows the complexity of studying the RCP even for paths. Thus, for a better understanding of this coloring model, it would be worth studying if the ideas of that proof could be extended to other families of graphs. Author contributions All authors contributed to the manuscript equally. Funding Funding for open access publishing: Universidad de Sevilla/CBUA D.G. and A.M. were supported by project PID2019-104129GB-I00 funded by New Results on the Robust Coloring Problem Page 19 of 20 122 MICIU/AEI/10.13039/501100011033 and PID2019-104129GB-I00/MCIN/AEI/ 10.13039/501100011033. Data availability Data sharing not applicable to this article as no datasets were generated or analyzed during the current study. Declarations Conflict of interest No conflicts of interest reported for this work. Open Access. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons. org/licenses/by/4.0/. References [1] Archetti, C., Bianchessi, N., Hertz, A.: A branch-and-price algorithm for the robust graph coloring problem. Discrete Appl. Math. 165, 49–59 (2014) [2] Barthelemy, J.P., Guenoche, A.: Trees and Proximity Representations. Wiley, New York (1991) [3] Burke, E.K., McCollum, B., Meisels, A., Petrovic, S., Qu, R.: A graph-based hyper-heuristic for educational timetabling problems. Eur. J. Oper. Res. 176(1), 177–192 (2007) [4] Chaitin, G.J.: Register allocation and spilling via graph coloring. In: SIGPLAN’82 Symposium on Compiler Construction, Boston, Mass., pp. 98–105 (1982) [5] Chartrand, G., Zhang, P.: Chromatic Graph Theory, 2nd edn. CRC Press, Boca Raton (2020) [6] Dey, A., Pradhan, R., Pal, A., Pal, T.: The fuzzy robust graph coloring problem. In: Proceedings of the 3rd International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 2014, pp. 805–803 (2014). Part of the Advances in Intelligent Systems and Computing Book Series (AISC, volume 327) [7] Furma´nczyk, H.: Equitable coloring of graph products. Opusc. Math. 26(1), 31– 44 (2006) [8] Furma´nczyk, H., Jastrzebski, A., Kubale, M.: Equitable colorings of graphs. Recent theoretical results and new practical algorithms. Arch. Control Sci. 26, 281–295 (2016) 122 Page 20 of 20 D. Garijo et al. Results Math [9] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979) [10] Garey, M.R., Johnson, D.S., So, H.C.: An application of graph coloring to printed circuit testing. IEEE Trans. Circuits Syst. 23, 591–599 (1976) [11] Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 3(1), 237–267 (1976) [12] Lim, A., Wang, F.: Robust graph coloring for uncertain supply chain management. In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS’05), vol. 3, pp. 81b (2005) [13] L´opez-Bracho, R., Ram´ırez, J., Zaragoza-Mart´ınez, F.J.: Algorithms for robust graph coloring on paths. In: Proceedings of the 2nd International Conference on Electrical and Electronics Engineering, pp. 9–12 (2005) [14] Meyer, W.: Equitable coloring. Am. Math. Mon. 80, 920–922 (1973) [15] Ogawa, H.: Labeled point pattern matching by Delaunay triangulation and maximal cliques. Pattern Recogn. 19(1), 35–40 (1986) [16] Pardalos, P.M., Mavridou, T., Xue, J.: The graph coloring problems: a bibliographic survey. In: Handbook of Combinatorial Optimization, vol. 2, pp. 331– 395. Kluwer Academic Publishers (1998) [17] Smith, D.H., Hurley, S.: Bounds for the frequency assignment problem. Discrete Math. 167–168, 571–582 (1997) [18] Wang, F., Xu, Z.: Metaheuristics for robust graph coloring. J. Heuristics 19, 529–548 (2013) [19] Y´a˜nez, J., Ram´ırez, J.: The robust coloring problem. Eur. J. Oper. Res. 148, 546–558 (2003) [20] Y¨uceo˘glu, B., Sahin, G., van Hoesel, S.P.M.: A column generation based algorithm for the robust graph coloring problem. Discrete Appl. Math. 217, 340–352 (2017) Delia Garijo, Alberto M´arquez and Rafael Robles Departamento de Matem´atica Aplicada I Universidad de Sevilla Avda. Reina Mercedes s/n 41012 Seville Spain e-mail: [email protected]; [email protected]; [email protected] Received: May 28, 2023. Accepted: February 7, 2024. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.