Problem on Graph Classes
Paloma T. Lima
Department of Informatics, University of Bergen, Norway [email protected]
Erik Jan van Leeuwen
Department of Information and Computing Sciences, Utrecht University, The Netherlands [email protected]
Marieke van der Wegen
Department of Information and Computing Sciences, Utrecht University, The Netherlands Mathematical Institute, Utrecht University, The Netherlands
Abstract
Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. In theRainbow Vertex Coloring (RVC)problem we want to decide whether the vertices of a given graph can be colored with at mostkcolors so that the graph becomes rainbow vertex-connected. This problem is known to beNP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixedp≥3 both variants of the problem becomeNP-complete when restricted to split (S3, . . . , Sp)-free graphs, whereSq denotes theq-sun graph.
2012 ACM Subject Classification Mathematics of computing→Graph theory Keywords and phrases rainbow vertex coloring, permutation graphs, powers of trees Digital Object Identifier 10.4230/LIPIcs.MFCS.2020.63
1 Introduction
Graph coloring is a classic problem within the field of structural and algorithmic graph theory that has been widely studied in many variants. An example is the rainbow coloring problem, which is an edge coloring problem [2, 11, 13]. One recent variant was defined by Krivelevich and Yuster [9] and has received significant attention: therainbow vertex coloring problem. A vertex-colored graph is said to berainbow vertex-connected if between any pair of its vertices, there is a path whose internal vertices are colored with distinct colors. Such a path is called arainbow path. Note that this vertex coloring does not need to be a proper one; for instance, a complete graph is rainbow vertex-connected under the coloring that assigns the same color to every vertex. TheRainbow Vertex Coloring (RVC) problem takes as input a graphGand an integerkand asks whether Ghas a coloring with kcolors under which it is rainbow vertex-connected. The rainbow vertex connection number of a graphGis the smallest number of colors needed in one such coloring and is denoted rvc(G).
More recently, Li et al. [12] defined a stronger variant of this problem by requiring that the rainbow paths connecting the pairs of vertices are also shortest paths between those pairs. In
© Paloma T. Lima, Erik Jan van Leeuwen, and Marieke van der Wegen;
licensed under Creative Commons License CC-BY
this case we say the graph isstrong rainbow vertex-connected. The analogous computational problem is calledStrong Rainbow Vertex Coloring (SRVC)and the corresponding parameter is denotedsrvc(G).
Both theRVCand theSRVC problems areNP-complete for everyk≥2 [4, 3, 5], and remainNP-complete even on bipartite graphs and split graphs [7]. Both problems are also NP-hard to approximate within a factor ofn1/3− for every >0, even when restricted to bipartite graphs and split graphs [7]. Contrasting these results, it was shown thatRVCand SRVCare linear-time solvable on bipartite permutation graphs and block graphs [7], and on planar graphs for every fixedk[10]. In fact, ifk is fixed, both problems are also solvable in linear time on graphs of constant treewidth and in cubic time on graphs of constant clique-width, as they can be expressed in monadic second order logic [5]. Furthermore, they are also solvable in linear time on graphs of vertex cover at mostp, for any fixedp[5]. Finally, RVCis also known to be linear time solvable on interval graphs [7].
The above mentioned results on bipartite permutation graphs and interval graphs led Heggernes et al. [7] to formulate the following conjecture concerning diametral path graphs.
A graphGis adiametral path graph if every induced subgraphH has a diametral pathP that is dominating. Recall that adiametral pathis a shortest path whose length is equal to the diameter, and thatdominating means that every vertex either is inP, or is adjacent to a vertex inP.
IConjecture 1(Heggernes et al. [7, Conjecture 15]). LetGbe a diametral path graph. Then rvc(G) = diam(G)−1.
In this context, it is interesting to remark that both bipartite permutation graphs and interval graphs are diametral path graphs, and that Heggernes et al. [7] showed that the conjecture is true for these graphs.
We remark that similar bounds were studied for the edge variant of the problem, in which we want to color the edges of a graph in such a way that every pair of vertices is connected by a path whose edges received pairwise distict colors (a rainbow path). For instance, it is known that AT-free graphs (a subclass of diametral path graphs) can be rainbow edge colored with diam(G) + 3 colors. However, there are examples of such graphsGthat need diam(G) + 2 colors to be rainbow edge colored [16].
Our Results. 1 Our main contribution is to show that the above conjecture is true for permutation graphs.
ITheorem A (=Theorem 17). IfGis a permutation graph on nvertices, then rvc(G) = diam(G)−1 and the corresponding rainbow vertex coloring can be found inO(n2)time.
This generalizes the earlier result on bipartite permutation graphs [7]. The proof of our result follows from a thorough investigation of shortest paths in permutation graphs. We show that there are two special shortest paths that ensure that a rainbow vertex coloring with diam(G)−1 colors can be found.
We also investigate the rainbow vertex connection number of chordal graphs further. As the problem isNP-hard and hard to approximate on split graphs [7], the hope for polynomial- time solvability rests either within subclasses of split graphs or other chordal graphs that are not inclusion-wise related to split graphs (such as the previously studied interval graphs and block graphs [7]). We make progress in both directions. First, we show that the problem is polynomial-time solvable on split strongly chordal graphs.
1 Statements marked with♠had their proofs omitted due to space constraints.
ITheorem B(=Theorem 20). If Gis a split strongly chordal graph with `cut vertices, then rvc(G) =srvc(G) = max{diam(G)−1, `}.
In order to obtain the above result, we exploit an interesting structural property of split strongly chordal graphs. Namely, ifGis a split strongly chordal graph with cliqueK and independent setS, there exists a spanning tree ofG[K] such that the neighborhood of each vertex ofS induces a subtree of this tree.
Second, we show thatRVC remains polynomial-time solvable on powers of trees. This proof is based on a case analysis, depending on whether the diameter of the tree is a multiple of the power and how many long branches the tree has. In some cases diam(G)−1 many colors are enough to rainbow vertex color these graphs, but surprisingly this is not always true. There are graphs in this graph class that actually require diam(G) colors in order to be rainbow vertex colored. We provide a complete characterization of such graphs, as well as a polynomial time algorithm to optimally rainbow vertex color any power of tree.
I Theorem C (=Theorem 26). If G is a power of a tree, then rvc(G) ∈ {diam(G)− 1,diam(G)}, and the corresponding optimal rainbow vertex coloring can be found in time that is linear in the size ofG.
2 Preliminaries
Whenever we write graph, we will mean a finite undirected simple graph. We assume throughout that all graphs are connected and have at least four vertices.
Let G= (V, E) be a graph. For two verticesu, v∈V, we useu∼vto denote thatuand v are adjacent. For a vertexv∈V, we writedG(v) for its degree. For a subgraphH ofG, we writeVH for the set of vertices ofH. Specifically, for a pathP in G, we write VP for the vertices ofP. IfX ⊆V, then byG[X] we denote the subgraph ofGinduced byX, that is, G[X] = (X, E∩(X×X)). We useN(v) ={u∈V |u∼v}andN[v] =N(v)∪ {v}.
The length of a pathP equals the number of edges ofP. The distancedG(u, v) is the length of a shortestu, v-path inG. If the graphGis clear from the context, we simply write d(u, v). Thediameter diam(G) ofGis the length of the longest shortest path between two vertices inG, that is, diam(G) = max{dG(u, v)|u, v∈V}. Acenterof a graphGis a vertex c such that max{dG(c, v)|v∈V} is minimum among all vertices ofG. Note that a graph can have multiple centers and that a tree can have at most two.
A graph Gis a permutation graph if it is an intersection graph of line segments between two parallel lines (see Figure 1). The set of line segments that induce the permutation graph is called anintersection model. Alternatively, ifGhasnvertices, then there is a permutation σof{1, . . . , n} such that vertexiand vertex j withi < j are adjacent inGif and only ifj comes beforeiin σ.
A graphGis achordal graph if every cycleC={c1, . . . , c`}on `≥4 vertices has a chord, meaning an edge between two non-consecutive vertices of the cycle.
A graph Gis asplit graphifVG can be split into two sets,KandS, such thatKinduces a clique inGandS induces an independent set inG.
For any k≥3, we denote bySk thek-sun on 2kvertices, that is, a graph with a clique c1, . . . , ck onkvertices and an independent setv1, . . . , vkofkvertices such thatviis adjacent to ci andci+1 for every 1≤i < k andvk is adjacent tock andc1. A graphGis astrongly chordal graph if it is chordal and every even cycleC has a chorduvsuch that the distance inC betweenuandv is odd. The strongly chordal graphs are exactly the chordal graphs which have no induced subgraphs isomorphic to ak-sun for anyk≥3.
v1
t(v1)
b(v1)
v2 v3 v4
L1
L2
v2
v3
v4
v1
Figure 1An intersection model and the corresponding permutation graph.
Thek-th power of a graphGfork≥1, denoted by Gk, is the graph on the same vertex set ofGwhereu∼v inGk if and only if there is a path of length at mostk fromuto vin G. In particular,G1=G. IfGis a tree, thenGk is a chordal graph for anyk≥1.
Finally we make the following observation about diameter two graphs, which follows from the fact that we can color all the vertices ofGwith the same color.
IObservation 1. If diam(G)≤2, then srvc(G) =rvc(G) = 1.
3 Permutation graphs
In this section, we consider rainbow colorings on permutation graphs. LetGbe a permutation graph. LetL1 andL2 be two parallel lines in the plane and for eachv∈VG, letsv be the segment associated tov in the intersection model (see Figure 1). We denote by t(v) the extreme ofsvinL1, that ist(v) =sv∩ L1, and we refer tot(v) as the top end point ofsv. By b(v) we denote the extreme ofsv inL2, the bottom end point ofsv. Throughout, we assume that an intersection model is given; otherwise, one can be computed in linear time [14].
Whenever we write “uintersects v” for two verticesuandv, we meansu intersectssv. For two verticesuandv, withu6=v, there are several options for u, v in the intersection model. If
t(u)< t(v) andb(u)> b(v), thenu∼v, t(u)> t(v) andb(u)< b(v), thenu∼v,
t(u)< t(v) andb(u)< b(v), then we say “uis left ofv” and writeu≺v, t(u)> t(v) andb(u)> b(v), then we say “uis right ofv” and writeuv.
We use the notation uv if t(u) ≤t(v) andb(u)≤b(v). Note that “≺” is a partial ordering on the vertices of the graph anduv does not implyuv.
For each pairu, v∈V(G), Mondal et al. [15] define twou-vpaths, one of which is shortest.
Define a pathXu,v as follows. Ifu∼v,Xu,vwill beu, v. Otherwise, assume without loss of generality thatu≺v. Start withx1=u. Of all verticesxthat intersect uwitht(x)> t(u), letx2 be the one with largestt(x2). If there is no vertexxthat intersectsuwitht(x)> t(u), we say that the pathXu,v does not exist. Otherwise, definexi, withi≥3, as follows. Ifxi−1
is incident tov, setxi=v and end the path. Otherwise, if iis even (resp. odd), letxi be the vertex that intersectsxi−1 wheret(xi) (resp.b(xi)) is largest.
Notice that it cannot be thatxi−2=xi, or Gwould not be connected.
Analogously, we define the pathYu,v. This path starts withy1=u. Ifuintersectsv, set y2=v and end the path. Otherwise, lety2 be the vertex that intersectsuwith largestb(y2), ifb(y2)> b(u) (otherwise the pathYu,v does not exist).
If yi−1 intersectsv, set yi =v and end the path. Otherwise, the next vertexyi is the vertex that intersectsyi−1 with largestb(yi) (resp.t(yi)) ifiis even (resp. odd). Notice that it cannot be thatyi−2=yi, orGwould not be connected.
pk−1 u pk
v
Figure 2If a vertexvin layerLk+1 intersect a vertexuin layerLk, then it also intersectspk. See Lemma 7.
The paths we just defined satisfy the following property. Let z1, z2, z3, . . . , za be a path.
For all 2≤i≤a,
t(zi)> t(zi−1) andb(zi)< b(zi−1) ifi is even, (1) t(zi)< t(zi−1) andb(zi)> b(zi−1) ifi is odd, (2) or, for all 2≤i≤a,
t(zi)< t(zi−1) andb(zi)> b(zi−1) ifi is even, (3) t(zi)> t(zi−1) andb(zi)< b(zi−1) ifi is odd. (4) Note that Equations (1) and (2) hold forXu,v, by definition, and that Equations (3) and (4) hold forYu,v, by definition.
ILemma 2(♠,Mondal et al. [15]). Xu,v orYu,v is a shortestu, v-path.
We define two special paths P and Q. ForP, let p1 be the vertex such that t(p1) is smallest among all vertices ofG. Perform the same process as in the construction ofXp1,·: fori≥2, if iis even (resp. odd), letpi be the vertex that intersectspi−1 wheret(pi) (resp.
b(pi)) is largest. Let P denote the resulting path and let pd denote the last vertex of P. Observe thatP =Xp1,pd.
ForQ, letq1 be the vertex such thatb(q1) is smallest among all vertices ofG. Perform the same process as in the construction ofYq1,·: fori≥2, ifiis even (resp. odd), letqi be the vertex that intersectsqi−1 whereb(qi) (resp.t(qi)) is largest. LetQdenote the resulting path and letqd0 denote the last vertex ofQ. Observe thatQ=Yq1,qd0.
ICorollary 3(♠). P is a shortestp1, pd-path andQ is a shortestq1, qd0-path.
We will prove some more useful properties about the pathsP andQ.
ILemma 4(♠). Letvt, resp.vb, be the segment that has the rightmost top, resp. bottom, end point. Then pd=vt and pd−1=vb ifdis even, and vice versa if dis odd. Furthermore, we have qd0 =vb andqd0−1=vt ifd0 is even, and vice versa if d0 is odd.
ILemma 5(♠). The setsVP\ {pd} andVQ\ {qd0} are dominating sets ofG.
I Lemma 6 (♠). It holds that d= diam(G) or d = diam(G) + 1, and d0 = diam(G) or d0= diam(G) + 1.
Now we start a breadth-first search from p1. Call the layersL1, L2, . . . , Lr. SinceP is a shortest path, it follows thatpi∈Li for everyi. Thusr≥d. SinceVP\ {pd}is a dominating set, we conclude thatr=d, thus the layers of the breadth-first search areL1, L2, . . . , Ld. We also start a breadth-first search inq1, and call the layersM1, M2, . . . , Md0. Again, we have thatqi∈Mi for everyi. A nice property of the pathP is that every vertexpi is adjacent to all vertices in the next layerLi+1.
p1
L1
p2
L2
p3
L3
. . . pd−1
Ld−1
pd
Ld
Figure 3The layers of the BFS, the layersL1, L2, . . . , Ld−1 are all assigned a different color. See Lemma 8.
ILemma 7. For everyi, it holds thatLi+1⊆N(pi)andMi+1⊆N(qi).
Proof. We will prove a somewhat stronger result by induction, namely thatLi+1⊆N(pi) and ifiis even (resp. odd) we have that for every uin Li+1:
t(u)< t(pi) andb(u)> b(pi) (resp. t(u)> t(pi) andb(u)< b(pi)). (5) We use a proof by induction. The first layerL1 contains onlyp1. It is clear that every vertex in the second layerL2 is a neighbour ofp1. Moreover, by the definition ofp1, we have thatt(u)> t(p1) for allu∈L2, and thusb(u)< b(p1).
Suppose thatLi+1⊆N(pi) and Equation (5) holds for everyi < k. Letv be a vertex in Lk+1. We know thatv does not intersectpk−1, otherwisev would be contained inLk. So we know thatt(v)> t(pk−1) andb(v)> b(pk−1). Sincev is in layerLk+1,v intersectsufor someu∈Lk (see Figure 2). So we either have thatt(v)< t(u) andb(v)> b(u) or we have t(v)> t(u) andb(v)< b(u). If k is even (resp. odd), we havet(v)< t(u) andb(v)> b(u) (resp.t(v)> t(u) andb(v)< b(u)), otherwise, by the induction hypothesis,v would intersect pk−1. By the induction hypothesis uintersects pk−1, so by the definition of pk, we have thatt(pk)≥t(u) (resp. b(pk)≥b(u)). It follows thatt(v)< t(pk) (resp.b(v)< b(pk)). We know that b(pk)< b(pk−1) (resp. t(pk) < t(pk−1)), thus b(v)> b(pk) (resp.t(v) > t(pk)).
We conclude thatv intersectspk, andt(v)< t(pk) andb(v)> b(pk) (resp.t(v)> t(pk) and b(v)< b(pk)). SoLk+1⊆N(pk) for everyk. The proof thatMk+1⊆N(qk) is analogous. J For an illustration of the structure ofG, see Figure 3. If d= diam(G) ord0= diam(G), we will colorGlayer by layer to obtain a rainbow coloring.
ILemma 8. If d= diam(G) ord0= diam(G), thenrvc(G) = diam(G)−1.
Proof. Assume thatd= diam(G). Consider the following coloring (see Figure 3): c(v) =i ifv ∈Li, 1≤i ≤d−1, andc(v) = 1 otherwise. This coloring uses d−1 = diam(G)−1 colors. We claim that it is a rainbow coloring. Letuandv be two vertices. Thenu∈Li, v ∈ Lj for some i, j. Without loss of generality, assume that i ≤ j. Ifu =pi, then, by Lemma 7, the pathp1, p2, . . . , pj−1, v is a rainbow path. If i >1, again by Lemma 7, the pathu, pi−1, pi, . . . , pj−1, vis a rainbow path. We conclude thatrvc(G) = diam(G)−1. The
proof ford0 = diam(G) is analogous. J
Consider the case whered=d0= diam(G) + 1. In this case, we will still color the layers of a breadth-first search that starts atp1, but we have to reuse the color of the first layer for layerLd−1. We consider the coloring: c(v) =iifv∈Li, 1≤i≤d−2, c(v) = 1 ifv∈Ld−1, andc(v) = 2 ifv∈Ld. We will show that this is a rainbow coloring. For almost everyuand v, we readily construct a rainbow path using pathP.
p1
1
p2
2
p3
3
. . . pd−2
d−2
pd−1
1
pd=qd−1
2 q1
q2 qd−3 qd−2
u v
Figure 4 The numbers indicate the colors of the layers. If u ∼ q1 and v ∼ qd−1, the path u, q1, p2, . . . , qd−2, v is a rainbow path. Ifu∼q2 andvqd−2, the pathu, q2, p3, . . . , qd−1, v is a rainbow path. See Lemma 14.
ILemma 9(♠). For the following uandv, there exists a rainbow path:
1. foru=pi, andv arbitrary,
2. foru∈Li withi≥3, andv∈Lj with j≥3, 3. foru∈L2, andv /∈Ld,
4. foru∈L2,u∼p2, andv∈Ld.
There are some vertices uandv, for which we did not yet construct a rainbow path. The case that is left, is the following:
5. foru∈L2,up2, andv∈Ld.
The path viaP,u, p1, p2, . . . , pd−1, v, does not suffice in this case, since it usesp1 andpd−1, which are both colored with color 1. So this is not a rainbow path. For some cases we show that a similar path viaQis a rainbow path. For other cases, we show that Xu,v orYu,v is a rainbow path.
ILemma 10(♠). If u∈L2 andup2, thenu∼q1 or u∼q2.
ILemma 11(♠). If d=d0= diam(G) + 1, thenpd=qd−1 andpd−1=qd.
ICorollary 12(♠). If d=d0= diam(G) + 1, it holds that qi∈Li+1, for every1≤i < d.
I Lemma 13 (♠). If d = d0 = diam(G) + 1, then for every v ∈ Ld, if v qd−2, then v∼qd−1.
Now we can prove for even more verticesuandvthat there is a rainbow path from uto v, using pathQ, see also Figure 4.
ILemma 14. For the following verticesuandv, there is a rainbow path:
5a. foru∈L2,up2,v∈Ld, andv∼qd−2,
5b. foru∈L2,up2,v∈Ld, andvqd−2,u∼q2.
Proof. 5a. By Lemma 10, we know thatu∼q1 oru∼q2. By Corollary 12, we know that q1, q2, . . . , qd−2 are in layers L2, L3, . . . , Ld−1, each vertex in a different layer. So, either u, q1, q2, . . . , qd−2, vor u, q2, q3, . . . , qd−2, v is a rainbow path.
5b. By Lemma 13, we know thatv∼qd−1. By Corollary 12, we know thatq1, q2, . . . , qd−2 are in layersL2, L3, . . . , Ld−1, each vertex in a different layer. The pathu, q2, q3, . . . , qd−1, v
is a rainbow path. J
Now there is still one case of verticesuandv for which we did not prove yet that there is a rainbow path. Namely:
5c. foru∈L2,up2,v∈Ld, andvqd−2,uq2.
For this last case we can show that eitherXu,vor Yu,v is a rainbow path.
ILemma 15 (♠). If u∼p1,up2 anduq2, thenu≺p2.
ILemma 16. Foruandv satisfying case 5c, there is a rainbow path.
Proof. We distinguish two cases, based on Lemma 2: eitherXu,v is a shortestu, v-path or Yu,v is a shortestu, v-path.
Suppose thatXu,v is a shortest u, v-path. Notice thatXu,v has at least one vertex in every layerL2, L3, . . . , Ld. SinceXu,v has length at most d−1, there is at most one layer which contains two vertices ofXu,v. It is clear thatx1=uis in layerL2. We will show that x2 is in layerL2as well. By definition ofx2, we have t(x2)> t(u) andb(x2)< b(u). Since u∼p1 andp1 has the leftmost top end, we know that t(u)> t(p1) andb(u)< b(p1). We conclude thatt(x2)> t(p1) andb(x2)< b(p1), thusx2∼p1. So we see thatx1 andx2are both in layerL2, so all internal vertices ofXu,v are in different layers. SoXu,v is a rainbow path.
Suppose thatYu,v is a shortestu, v-path. WriteYu,v=u, y2, y3, . . . , yα−1, v. Thenα=d orα=d−1; note that α≤diam(G) + 1 =dand thatd−1≤αbecause Yu,v contains a vertex from every layer. We prove by induction thatyi∈Li+1 for all 2≤i≤α−1.
Sincey2 andp1 both intersectu, by the definition ofy2, it follows thatb(y2)≥b(p1). See Figure 5. Ify2=p1, thenyu,v=u, p1, p2, . . . , pd−1, v. Notice that the length of this path is d= diam(G) + 1. This yields a contradiction with the fact thatYu,v is a shortestu, v-path.
Hence,y26=p1, andb(y2)> b(p1). Sincep1 is the vertex with the leftmost top end, we see thatt(p1)< t(y2). Hencey2p1. Sincey2does not intersectp1, it follows thaty2∈/L2.
By the definition ofy2, we know thatt(y2)< t(u). By Lemma 15, it holds thatt(u)< t(p2), thust(y2)< t(p2). Moreover,b(y2)> b(p1)> b(p2) (by Equation (1)). Hence,y2intersects p2. We conclude thaty2∈L3.
Suppose that for alli < k, for somek >2, it holds thatyi pi−1 andyi∈Li+1. Now consideryk. Suppose thatkis even. By the induction hypothesis and Lemma 7, we know that yk−1∼pk−1, sinceyk−1∈Lk. By definition ofyk, it follows that b(yk)≥b(pk−1). And by Equation (1), we know thatb(pk−1)> b(pk), thusb(yk)> b(pk). Similarly, by the definition ofpk, we know thatt(pk)≥t(yk−1). And by Equation (3), we know thatt(yk)< t(yk−1), hencet(pk)> t(yk). We conclude thatpk intersectsyk. It follows thatyk is in layerk−1, k ork+ 1.
Notice that ifyk∈Lk−1, then the length ofYu,vis at leastd= diam(G) + 1. This yields a contradiction with the fact thatYu,vis a shortestu, v-path. Thusyk ∈/ Lk−1. Suppose that yk∈Lk. Thenyk intersectspk−1. We have seen thatb(yk)≥b(pk−1), thust(yk)< t(pk−1).
By Equation (2), we haveb(pk−1)> b(pk−2), Thus b(yk)> b(pk−2). By Equation (2), we also have thatt(pk−1)< t(pk−2), thust(yk)< t(pk−2). It follows thatyk∼pk−2. This yields a contradiction with the assumption thatyk ∈Lk. We conclude thatyk ∈Lk+1.
The case forkodd is analogous. Sinceyi∈Li+1 for all internal verticesyi of Yu,v, we
conclude thatYu,v is a rainbow path. J
I Theorem 17 (=Theorem A). For every n-vertex permutation graph G, it holds that rvc(G) = diam(G)−1. Moreover, we can compute an optimal rainbow vertex coloring in O(n2)time.
Proof. By Lemma 6 we know that eitherd = diam(G) or d = diam(G) + 1, and either d0 = diam(G) or d0 = diam(G) + 1. If d= diam(G) or if d0 = diam(G), we have seen a rainbow coloring ofGwith diam(G)−1 colors in Lemma 8. If bothdandd0equal diam(G)+1, then we have seen a coloring ofGwith diam(G)−1 colors. Lemmas 9, 14 and 16 show that this coloring is indeed a rainbow coloring. We conclude thatrvc(G) = diam(G)−1.
p1
u y2
p2
p3
y3
Figure 5Vertexy2 is in layerL3. See Lemma 16.
Assume that we are given a permutation model of the graph and thus know the values t(v) andb(v) for each vertexv∈V(G). Otherwise, a permutation model can be computed in linear time [14]. First, computedandd0. Following the description ofP andQ, this takes linear time. Computing the diameter ofGtakes O(n2) time using the algorithm of Mondal et al. [15]. The colorings given by Lemma 8 and before Lemma 9 can each be computed in linear time through a breadth-first search. By the preceding arguments, an optimal rainbow
vertex coloring can be computed inO(n2) time. J
4 Split strongly chordal graphs
In this section, we show thatRVCandSRVCare polynomial-time solvable on split strongly chordal graphs. We show this result is tight in the sense that both problems areNP-complete on split graphs if we forbid any finite family of suns.
In order to prove our next theorem we will use the following property of dually chordal graphs, a graph class that contains that of strongly chordal graphs [1].
ILemma 18. (Brandstädt et al. [1]) A graph G is dually chordal if and only ifG has a spanning tree T such that all maximal cliques of Ginduce a subtree ofT.
We show a tree with a stronger property exists in split strongly chordal graphs.
ILemma 19(♠). LetG= (V, E)be a connected split strongly chordal graph, withV =K∪S, where K is a clique and S is an independent set. ThenGhas a spanning treeT such that every maximal clique ofGinduces a subtree ofT and every vertex of S is a leaf ofT. ITheorem 20 (=Theorem B). IfGis a split strongly chordal graph with`cut vertices, then rvc(G) =srvc(G) = max{diam(G)−1, `}.
Proof. Let G= (V, E) be a split strongly chordal graph, withV =K∪S, where K is a clique and S is an independent set. Note that if diam(G)≤ 2, we can (strong) rainbow colorGby assigning the same color to all the vertices. Notice that in this case`≤1, thus rvc(G) =srvc(G) = max{diam(G)−1, `}.
Assume then that diam(G) = 3 (recall that ifGis a split graph, then diam(G)≤3). By Lemma 19,Ghas a spanning treeT such that every maximal clique ofGinduces a subtree of T and every vertex of S is a leaf ofT. Let T denote the subtree of T induced by the vertices ofK, that is, the subtree of T obtained by the deletion of the leaves corresponding to vertices ofS. Note thatT is a tree withVT =K. We will now use the treeT to provide a (strong) rainbow coloring ofG.
BClaim 1 (♠). For every x∈S, N(x) induces a subtree ofT.
BClaim 2. IfGis 2-connected, thensrvc(G) =rvc(G) = diam(G)−1.
Proof. Note that diam(G)−1 = 2. Color the vertices of K according to a proper 2-coloring of the vertices ofT, and give arbitrary colors to the vertices ofS. Letφbe the coloring ofG obtained in this way. Note thatφis indeed a (strong) rainbow coloring ofG. To see this, let u, v∈V be such thatdG(u, v) = 3. SinceGis a split graph, we have thatu, v∈S. SinceG is 2-connected,|N(u)| ≥2 and |N(v)| ≥2. Moreover, sinceN(u) andN(v) induce subtrees ofT, we know that these two sets are not monochromatic underφ. Thus, there arex∈N(u) andy ∈N(v) s.t.φ(x)6=φ(y), which showsuxyv is a rainbow (shortest) path betweenu
andv. C
We now consider the case in whichGhas cut vertices. LetC⊂V be the set of cut vertices ofG. Consider a proper 2-coloringφofT. If there existc1, c2∈C such thatφ(c1)6=φ(c2), then we can obtain a (strong) rainbow coloring forG with` colors by assigning distinct colors in the set{3, . . . , `}to the remaining cut vertices ofG. Note that with this coloring ofT, it holds that for everyw∈S, if|N(w)|>1, thenN(w) is not monochromatic underφ.
Since all the cut vertices were assigned distinct colors, by the same argument used in the 2-connected case, this is indeed a (strong) rainbow coloring ofG. Note that this reasoning also applies if|C|= 1, so from now on we may assume|C| ≥2.
If all the vertices ofC were assigned the same color, sinceφwas a proper 2-coloring ofT, we have that for everyx, y∈C,dT(x, y)≥2. Letc1, c2∈Cbe two cut vertices such that the unique path connectingc1andc2inT contains no other vertex ofC. Letzbe the vertex adjacent toc1 in this path. Note thatz /∈C. We will consider the following coloringφ0 ofT. Letφ0(c1) =φ0(z) = 1. Now we extendφ0 by considering a proper 2-coloring of the subtree ofT rooted in c1 (resp.z) that assigns color 1 to the vertexc1(resp. z). Note that now we haveφ0(c2) = 2. Finally, assign distinct colors from{3, . . . , `}to the vertices ofC\ {c1, c2}.
To obtain a (strong) rainbow coloring ofG, we color the vertices ofK according toφ0 and give arbitrary colors to the vertices ofS.
BClaim 3 (♠). φ0 is a (strong) rainbow coloring ofG.
Sinceφ0 uses`colors, this concludes the proof. J
We now show that both RVC andSRVC are NP-complete if we only forbid a finite number of suns. In what follows, we make use of the same reduction of Heggernes et al. [7]
for split graphs. Their reduction is fromHypergraph Coloring. In our case, we start with an instance of Graph Coloringrestricted to (C3, . . . , Cp)-free graphs, a problem that was shown to beNP-complete by Král’ et al [8] (see also [6]) for every fixedk≥3. We can see an inputG= (V, E) of Graph Coloring as a hypergraph in which every hyperedge has size two. We perform the same construction as Heggernes et al. [7], starting with an (C3, . . . , Cp)-free instance of Graph Coloring.
I Theorem 21 (♠). For any fixed p ≥ 3, RVC and SRVC are NP-complete on split (S3, . . . , Sp)-free graphs for any fixedp≥3.
5 Powers of trees
In this section we study powers of trees. LetT be a tree, and z in the center ofT. Let e=zvbe an edge that is incident toz, withv not in the center. Wheneis removed from the tree, the tree will fall apart in two parts, abranch is the part that does not containz. If the center ofT contains only one vertex, the number of branches equals the degree ofz. We distinguish between squares and higher powers of trees. We first consider squares of trees.
p2=q2
p1=q1
v1
p3
p4
v2
q3
q4
v3
Figure 6A graphT for whichT2 needs diam(T2) colours, see Lemma 22.
Two trivial lower bounds for the rainbow coloring number of a graph Gare the number of cut vertices inGand diam(G)−1. In squares of trees we found graphs that need more than diam(T2)−1 colors. Notice that squares of trees are 2-connected, so there are no cut vertices.
ILemma 22. LetT be a tree such that the center ofT consist of a single vertexz,T has diameter at least 6, and there are at least three branches from the center with maximum length. Thensrvc(T2)≥rvc(T2)≥diam(T2).
Proof. Letv1, v2, andv3 be three vertices with maximum distance toz in three different branches. We consider the case that diam(T2) is odd. There is a unique shortest path P =v1, p1, p2, . . . , pk, v2 fromv1 tov2inT2. Analogously, there is a unique shortest path Q =v1, q1, q2, . . . , qk, v3 from v1 tov3 in T2. Notice thatq1 = p1, q2 =p2, . . ., qj =pj, wherej =bdiam(T2 2)c. That is,P andQuse the same vertices in the branch of v1. The unique shortest pathRinT2 fromv2 tov3isv2, pk, . . . , pj+1, qj+1, . . . , qk, v3. See Figure 6.
We give a proof by contradiction. Let cbe a rainbow vertex coloring that uses at most diam(T2)−1 colors. Notice that the pathsP,Q, andRhave length diam(T2). Therefore, for each of these paths, all internal vertices are assigned different colors and all colors appear in the path. Since the firstj vertices of the pathsP andQare equal, we see that the colors used for pj+1, . . . , pk are the same as the colors used for qj+1, . . . , qk. Since diam(T)≥6, {pj+1, . . . , pk}and{qj+1, . . . , qk}are non-empty. Hence, there is a color that appears twice inR, which yields a contradiction. We conclude thatrvc(T2)≥diam(T2).
The case that diam(T2) is even is analogous. J
The class of graphs described in the statement of Lemma 22 needs exactly diam(T2) colors.
We define layeri as the set of all vertices with distancebdiam(T)/2c −ito the center ofT. For a vertexv, we writel(v) for the layer that it is contained in, so l(v) =bdiam(T)/2c −d, wheredis the distance ofvto the center ofT. Our upper bounds all use a coloring by layer.
ILemma 23 (♠). Let T be a tree such that the center of T consist of a single vertex, T has diameter at least6, and there are at least three branches from the center with maximum length. Thenrvc(T2) = diam(T2).
In squares of trees this is the only example that needs more than diam(T2)−1 colors. If tree T has diam(T)≤4, then diam(T2)≤2 and thusrvc(T2) = 1 by Observation 1. We distinguish two cases for the remaining trees.
ILemma 24. LetT be a tree such that the center of T consist of a single vertex,T has diameter at least6, and there are exactly two branches from the center with maximum length.
Thenrvc(T2) = diam(T2)−1.
Proof sketch (♠). Let B1 be one of the branches with maximum length. Let B2 be all other branches, together with the center vertex. Suppose that diam(T2) is odd. Consider the following coloringc. We colorB2per layer, using the color of layer 1 for the center as well. And we colorB1 similar, but with the colors of layer 1 and 2 swapped, and the colors of layers 3 and 4 swapped, etc. So, the colors used in the even layers ofB1 are exactly the colors of the odd layers ofB2 and vice versa. The number of colors used in this coloring equals diam(T2)−1.
Letuandv be two vertices ofT. Suppose thatuandv are both inBi, fori= 1,2, and assume thatl(u)≤l(v). Use the even layer to go fromuto the lowest common ancestorw and the odd layers to go fromw tov. This is a rainbow path since every layer has a unique color, except for the center vertex. And if the center vertex is contained in this path, no vertex of layer 1 is an internal vertex.
Ifu∈Bi andv∈Bj, withi6=j, consider the following path. Use the even layers to go fromuto the center and even layers to go from the center tov, but exclude the center itself from this path.
Suppose that diam(T2) is even. We slightly modify the coloringc: we color B2 per layer, and use the color of layer 1 for the center as well. And we colorB1 similar, but with the colors of layer 2 and 3 swapped, and the colors of layers 4 and 5 swapped, etc. The paths constructed above are rainbow paths in this coloring as well. J ILemma 25 (♠). LetT be a tree such that the center ofT consist of two vertices and T has diameter at least5. Then rvc(T2) = diam(T2)−1.
We further consider higher powers of trees and generalize the above results forTk for k≥3. Even though the corresponding statements are similar, we have to distinguish more cases in order to prove them. The proofs are deferred to the appendix. We then obtain the following theorem on all powers of trees.
ITheorem 26 (=Theorem C, ♠). IfG is a power of a tree, then rvc(G)∈ {diam(G)− 1,diam(G)}, and the corresponding optimal rainbow vertex coloring can be found in time that is linear in the size ofG.
6 Conclusion and open problems
We provided polynomial-time algorithms to rainbow vertex color permutation graphs, powers of trees, and split strongly chordal graphs. The algorithm provided for the latter class also works for the strong variant of the problem.
An interesting question to be answered towards solving Conjecture 1 is whetherRVCcan be solved in polynomial time on AT-free graphs, i.e. graphs that do not contain an asteroidal triple. Conjecture 1 has been proved true for interval graphs [7] and, in this work, for permutation graphs, both of which are important subclasses of AT-free graphs.
Another direction of research within graph classes lies in determining the complexity of RVCandSRVCon strongly chordal graphs. Note that both powers of trees and split strongly chordal graphs form subclasses of strongly chordal graphs for which RVC is polynomial-time solvable, as we show in this work. Finally, note that every strongly chordal graph is also a chordal graph, and the problems are known to beNP-hard when restricted to chordal graphs.
References
1 Andreas Brandstädt, F. Dragan, V. Chepoi, and V. Voloshin. Dually chordal graphs. SIAM Journal on Discrete Mathematics, 11:71–77, 2007.
2 Gary Chartrand, Garry L Johns, Kathleen A McKeon, and Ping Zhang. Rainbow connection in graphs. Mathematica Bohemica, 133(1):85–98, 2008.
3 Lily Chen, Xueliang Li, and Huishu Lian. Further hardness results on the rainbow vertex- connection number of graphs. Theoretical Computer Science, 481:18–23, 2013.
4 Lily Chen, Xueliang Li, and Yongtang Shi. The complexity of determining the rainbow vertex-connection of a graph. Theoretical Computer Science, 412(35):4531–4535, 2011.
5 Eduard Eiben, Robert Ganian, and Juho Lauri. On the complexity of rainbow coloring problems. Discrete Applied Mathematics, 246:38–48, 2018.
6 Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of coloring graphs with forbidden subgraphs. Journal of Graph Theory, 84:331–363, 2017.
7 P. Heggernes, D. Issac, J. Lauri, P. T. Lima, and E. J. van Leeuwen. Rainbow vertex coloring bipartite graphs and chordal graphs. InProceedings of MFCS’18, volume 117 ofLIPIcs, pages 83:1–83:13, 2018.
8 Daniel Král’, Jan Kratochvíl, Zsolt Tuza, and Gerhard J. Woeginger. Complexity of coloring graphs without forbidden induced subgraphs. InWG’01, pages 254–262, 2001.
9 Michael Krivelevich and Raphael Yuster. The rainbow connection of a graph is (at most) reciprocal to its minimum degree. Journal of Graph Theory, 63(3):185–191, 2010.
10 Juho Lauri.Chasing the Rainbow Connection: Hardness, Algorithms, and Bounds. PhD thesis, Tampere University of Technology, 2016.
11 X. Li, Y. Shi, and Y. Sun. Rainbow connections of graphs: A survey.Graphs and Combinatorics, 29:1–38, 2013. doi:10.1007/s00373-012-1243-2.
12 Xueliang Li, Yaping Mao, and Yongtang Shi. The strong rainbow vertex-connection of graphs.
Utilitas Mathematica, 93:213–223, 2014.
13 Xueliang Li and Yuefang Sun. An updated survey on rainbow connections of graphs - a dynamic survey. Theory and Applications of Graphs, 0(1):1–38, 2017. doi:10.20429/tag.2017.000103.
14 Ross M. McConnell and Jeremy P. Spinrad. Modular decomposition and transitive orientation.
Discrete Mathematics, 201(1):189–241, 1999. doi:10.1016/S0012-365X(98)00319-7.
15 Sukumar Mondal, Madhumangal Pal, and Tapan K. Pal. An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs. Journal of Mathematical Modelling and Algorithms, 2:57–65, 2003. doi:10.1023/A:1023695531209.
16 L. Sunil Chandran, Anita Das, Deepak Rajendraprasad, and Nithin M. Varma. Rainbow connection number and connected dominating sets. Journal of Graph Theory, 71(2):206–218, 2012. doi:10.1002/jgt.20643.
