2405.06446v1.pdf

Recoloring via modular decomposition ∗ † ‡...

Recoloring via modular decomposition ∗ † ‡ Manoj Belavadi Kathie Cameron Ni Luh Dewi Sintiari May 13, 2024 arXiv:2405.06446v1 [math.CO] 10 May 2024 Abstract The reconfiguration graph of the k-colorings of a graph G, denoted Rk (G), is the graph whose vertices are the k-colorings of G and two colorings are adjacent in Rk (G) if they differ in color on exactly one vertex. A graph G is said to be recolorable if Rℓ (G) is connected for all ℓ ≥ χ(G)+1. We use the modular decomposition of several graph classes to prove that the graphs in the class are recolorable. In particular, we prove that every (P5 , diamond)- free graph, every (P5 , house, bull)-free graph, and every (P5 , C5 , co-fork)-free graph is recolorable. 1 Introduction Let G be a finite simple graph with vertex-set V (G) and edge-set E(G). We assume that G is connected unless stated otherwise. We use n to represent the number of vertices in a graph. Two vertices u and v are adjacent in G if uv ∈ E(G). For a positive integer k, a k-coloring of G is a mapping from V (G) to a set of colors {1, 2,... , k} such that no two adjacent vertices receive the same color. We say that G is k-colorable if it admits a k-coloring, and the chromatic number of G, denoted χ(G), is the minimum number of colors required to color G. We say χ-coloring of G instead of χ(G)-coloring of G, when appropriate. The reconfiguration graph of the k-colorings, denoted Rk (G), is the graph whose vertices are the k-colorings of G and two colorings are adjacent in Rk (G) if they differ in color on exactly one vertex. A graph G is said to be k-mixing if Rk (G) is connected. Given a reconfiguration graph, we can ask the following questions: Is the reconfiguration graph connected? If so, what is the diameter of the reconfiguration graph? In this paper we focus on the connectivity of the reconfiguration graph of the k-colorings. We say a graph G is recolorable if Rℓ (G) is connected for all ℓ ≥ χ(G)+1. Deciding whether there exists a path between two colorings in Rk (G) is PSPACE-complete for k > 3 , and can be decided in polynomial time for k ≤ 3. In 2018, Wrochna proved that the problem remains PSPACE-complete for graph classes with bounded bandwidth, and hence for graph classes with bounded treewidth. This led researchers to study the problem for various restricted graph classes. In , a graph class known as k-color-dense graphs was introduced and it was proved that every k-color-dense graph is recolorable. The class of k- color-dense graphs includes the class of k-colorable chordal graphs. For a graph H, a graph G is H-f ree if no induced subgraph of G is isomorphic to H. In , it was proved that every H-free ∗ Department of Mathematics, Wilfrid Laurier University, Waterloo, ON, Canada, N2L 3C5. Email: [email protected]. ORCID: 0000-0002-3153-2339. Research supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant RGPIN-2016-06517. † Department of Mathematics, Wilfrid Laurier University, Waterloo, ON, Canada, N2L 3C5. Email: [email protected]. ORCID: 0000-0002-0112-2494. Research supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant RGPIN-2016-06517. ‡ Department of Informatics, Universitas Pendidikan Ganesha, Bali, Indonesia, 81116. Email: [email protected]. ORCID: 0000-0002-6562-4434. Research supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant RGPIN-2016-06517. 1 graph G is recolorable if and only if H is an induced subgraph of P4 or P3 +P1. For a collection of graphs H, G is H-free if G is H-free for every H ∈ H. Bonamy and Bousquet used the tree decomposition of graphs to show that every graph G is (tw(G)+2)-mixing, where tw(G) denotes the treewidth of the graph G. In this paper we use the modular decomposition of a graph G to prove that G is recolorable. A set S ⊆ V (G) is a module if 1 ≤ |S| ≤ |V (G)| and every vertex in V (G) \ S is either adjacent to every vertex of S or no vertex of S. A module S is said to be non-trivial if S contains at least two vertices. Note that for each v ∈ V (G), {v} is a trivial module in G. A graph G is prime if it does not contain any non-trivial module. By substituting a graph H for S ⊆ V (G) we mean taking the graph G-S and adding an edge between every vertex of H and every vertex of G-S that is adjacent to some vertex of S in G. Note that this is slightly different from the well-known definition of substituting a graph for a vertex. However, substituting a graph H for S ⊆ V (G) is equivalent to contracting the set S to a vertex v (and removing any loops and multiple edges created), and then applying the usual definition of substituting the graph H for the vertex v. A blowup of a graph G is a graph obtained by substituting non-empty cliques for some vertices of G. (a) diamond (b) house (c) bull (d) co-f ork Figure 1 A class of graphs G is said to be hereditary if for every G in G, every induced subgraph of G is also in G. Note that for a collection of graphs H, the class of H-free graphs is hereditary. In Section 3, we prove the following. Theorem 1. Let G be a hereditary class of graphs and let H be the set of prime graphs in G. If for all H ∈ H, every blowup of H is recolorable, then for all G ∈ G, G is recolorable. We use the above result in Section 4 along with the modular decomposition of several subclasses of P5 -free graphs to prove the following. Theorem 2. Every (P5 , diamond)-free graph is recolorable. Theorem 3. Every (P5 , house, bull)-free graph is recolorable. Note that there exist P5 -free graphs that are not recolorable. A graph G is said to be P4 -sparse if every set of five vertices in G induces at most one P4. The class of P4 -sparse graphs generalizes the class of P4 -free graphs. Jamison and Olariu gave a forbidden induced subgraph characterization for P4 -sparse graphs: A graph G is P4 -sparse if and only if G is (P5 , C5 , house, fork, co-fork, banner, co-banner)-free. In 1997, Fouquet and Giakoumakis introduced the class of semi-P4 -sparse graphs which is a generalization of the class of P4 -sparse graphs. A graph G is semi-P4 -sparse if G is (P5 , C5 , co-fork)-free. We prove the following. Theorem 4. Every semi-P4 -sparse graph is recolorable. Feghali and Fiala , proved that every 3-colorable (P5 , house, C5 )-free graph is recolorable and asked if every (P5 , house, C5 )-free graph is recolorable. We prove the following. Theorem 5. Every (P5 , house)-free graph is recolorable if and only if every (P5 , house, C5 )-free graph is recolorable. Section 5 contains some open questions. 2 2 Preliminaries A path in a graph is a sequence of distinct vertices vi and edges of the form v0 , v0 v1 , v1 ,... , vp−1 , vp−1 vp , vp. The length of a path is equal to the number of edges in the path. A graph is said to be connected if there exists a path between every pair of distinct vertices of the graph. A vertex v ∈ V (G) is said to be universal if v is adjacent to every vertex in V (G) \ {v}. We say a coloring α of G is reachable from a coloring β of G in Rℓ (G) if there is a path between α and β in Rℓ (G). Where A ⊆ V (G) and B ⊆ V (G), we say A is complete to B if every vertex in A is adjacent to every vertex in B. A set of mutually adjacent vertices in a graph is called a clique. A set of mutually non-adjacent vertices in a graph is called an independent set. Where α is a coloring of G and S ⊆ V (G), we use α(S) to denote the set of colors that appear on the vertices of S under α. Let Pn , Cn , and Kn denote the path, cycle, and complete graph on n vertices, respectively. Let Kp,q denote the complete bipartite graph with p vertices in one set of the bipartition and q vertices in the other. A graph H is said to be a subgraph of G, if V (H) ⊆ V (G) and E(H) ⊆ E(G). A subgraph of G induced by a subset S ⊆ V (G) is the subgraph of G with vertex-set S and edge-set all edges of G which have both ends in S; it is denoted by G[S]. An induced subgraph H of G is said to be proper if V (H) ⊂ V (G). For a subset S ⊆ V (G), we use G-S to denote the subgraph of G obtained by deleting the vertices of S from G. For a vertex v, we use G-v instead of G-{v}. For a subset M ⊆ E(G), we use G-M to denote the graph obtained by deleting M from G, that is, the graph with vertex-set V (G) and edge-set E(G)\M. The complement of a graph G, denoted co-G, is the graph with the same vertices as G such that two vertices are adjacent in co-G if and only if they are non-adjacent in G. A component of a graph G is a maximal connected subgraph of G. For two vertex-disjoint graphs G and H, the disjoint union of G and H, denoted by G + H, is the graph with vertex-set V (G) ∪ V (H) and edge-set E(G) ∪ E(H). For a positive integer r, we use rG to denote the graph consisting of the disjoint union of r copies of G. The join of two graphs G1 and G2 is the graph obtained from the disjoint union of G1 and G2 by adding edges from each vertex of G1 to every vertex of G2. If G is disconnected, then it is easy to see that G is recolorable if and only if every component of G is recolorable. So we may assume that G is connected when appropriate. We also note that if G is a join of two graphs G1 and G2 , then G is recolorable if both G1 and G2 are recolorable. 3 Modular Decomposition A module S is said to be maximal if S ⊂ V (G) and it is not contained in a larger module M ⊂ V (G). Two sets X and Y overlap if X-Y , Y -X, and X ∩ Y are all non-empty. If two modules S1 and S2 of G overlap, then it is easy to see that S1 -S2 , S2 -S1 , S1 ∩ S2 , and S1 ∪ S2 are also modules of G. If G is neither a join nor a disjoint union of two graphs, then any two maximal modules of G are disjoint, and hence V (G) can be partitioned into maximal modules S1 , S2 ,... , Sm. Partitioning V (G) into maximal modules can be done in linear-time; see for more information. Let G be a graph which is neither a join nor a disjoint union of two graphs; the skeleton of G, denoted G∗ , is the graph obtained by contracting each maximal module to a single vertex (and removing any loops and multiple edges created). It can also be obtained from G by recursively substituting a vertex for each maximal module in G. Note that G∗ is a prime subgraph of G, induced by a set containing exactly one vertex from each maximal module in G. For the remainder of this section, we use the following decomposition. Let G be a graph which is neither a join nor a disjoint union of two graphs. Let S1 ,... , Sm be a partition of V (G) into maximal modules. Note that Sp ∩ Sq = ∅ for all p 6= q, p and q ∈ [m]. Let χ(G) = k and let χ(G[Sp ]) = kp , for all p ∈ [m]. For a graph G, the clique skeleton of G is the graph obtained 3 from G by recursively substituting a clique Qp of size kp for each Sp in G, where p ∈ [m]. We use G(Q1 ,... , Qm ) to denote the clique skeleton of G. Similar operations have been defined in the literature, for example see. Let H = G(Q1 ,... , Qm ) be the clique skeleton of G. Then for any k-coloring α of G, there exists a k-coloring β of H such that β(Qp ) ⊆ α(Sp ), for all p ∈ [m]. Note that such a coloring β of H can be obtained by coloring each Qp with colors from the set α(Sp ), for all p ∈ [m]. Similarly, given any k-coloring β of H, there exists a k-coloring α of G such that for all p ∈ [m], α(Sp ) = β(Qp ). Thus χ(G) = χ(H). Note that the clique skeleton of a graph G is a blowup of the skeleton of G. Lemma 1. Let G be a graph such that V (G) can be partitioned into maximal modules S1 ,... , Sm. Assume every proper induced subgraph of G is recolorable. Let α and β be two χ-colorings of G such that for each Sp of G, α(Sp ) ⊆ β(Sp ). Then there is a path between α and β in Rℓ (G), for all ℓ ≥ χ(G)+1. Proof. Let G be a graph such that V (G) can be partitioned into maximal modules S1 ,... , Sm. Let γ be a coloring of G and let p ∈ [m]. For any vertex v ∈ Sp , since its neighbors not in Sp are complete to Sp , they will not be colored with a color from the set γ(Sp ) under γ. Let ℓ ≥ χ(G)+1 and let {1,... , ℓ} be the set of available colors. Let α and β be two χ-colorings of G such that α(Sp ) ⊆ β(Sp ), for all p ∈ [m]. Then there exists a color, say c, that does not appear on V (G) under either α or β. Since G[Sp ] is recolorable for all p ∈ [m], we can use the color c to recolor the vertices in Sp from α to β, for each p ∈ [m] one at a time, without changing the colors on vertices in Sj where j 6= p. Lemma 2. Let G be a graph such that V (G) can be partitioned into maximal modules S1 ,... , Sm. Let H = G(Q1 ,... , Qm ) be the clique skeleton of G. Let α be any χ-coloring of G. Let β1 and β2 be any two χ-colorings of H such that for each Sp of G, β1 (Qp ) ⊆ α(Sp ) and β2 (Qp ) ⊆ α(Sp ). Then there is a path between β1 and β2 in Rℓ (H), for all ℓ ≥ χ(H)+1. Proof. Assume the hypotheses. Let ℓ ≥ χ(H)+1. Let {1,... , ℓ} be the set of available colors. Since α is χ-coloring of G, there exists a color, say c, that does not appear on V (G) under α. Since β1 (Qp ) ⊆ α(Sp ) and β2 (Qp ) ⊆ α(Sp ), for all p ∈ [m], the color c also does not appear on V (H) under either β1 or β2. Since each Qp is a clique, it is recolorable. Recolor the vertices in Qp from β1 to β2 using the extra color c, for each p ∈ [m] one at a time, without changing the colors on vertices in Qj where j 6= p. Lemma 3. Let G be a graph such that V (G) can be partitioned into maximal modules S1 ,... , Sm. Let H = G(Q1 ,... , Qm ) be the clique skeleton of G. Let ℓ ≥ χ(G)+1. Let α be an ℓ- ′ coloring of G and let β be a χ-coloring of G. Let α be an ℓ-coloring of H such that for all ′ ′ ′ p ∈ [m], α (Qp ) ⊆ α(Sp ). Let β be a χ-coloring of H such that for all p ∈ [m], β (Qp ) ⊆ β(Sp ). ′ ′ If there is a path between α and β in Rℓ (G), then there is a path between α and β in Rℓ (H). Proof. Assume the hypotheses. Let P be a path between α and β in Rℓ (G). Let αi and αi+1 ′ be two ℓ-colorings of G, which are adjacent in P. Let αi be any ℓ-coloring of H such that for ′ ′ all p ∈ [m], αi (Qp ) ⊆ αi (Sp ). We prove that there is a path from αi to some ℓ-coloring of H, ′ ′ say αi+1 , in Rℓ (H) such that for all p ∈ [m], αi+1 (Qp ) ⊆ αi+1 (Sp ). Since αi and αi+1 are adjacent in Rℓ (G), they differ on a single vertex, say v. Without loss of generality, let v ∈ Sj for some j ∈ [m]. Note that there are no vertices in the closed neighborhood of v colored αi+1 (v) under the coloring αi of G. Thus, there are no vertices in the ′ ′ closed neighborhood of any vertex in Qj colored αi+1 (v) under the coloring αi of H. Let αi+1 ′ be the coloring obtained from αi by recoloring the vertex in Qj colored αi (v) with the color ′ ′ αi+1 (v). It follows that there is a path between αi and αi+1 in Rℓ (H) such that for all p ∈ [m], ′ αi+1 (Qp ) ⊆ αi+1 (Sp ). Thus, if there exists a path between α and β in Rℓ (G), then there exists ′ a path from α to some coloring β ∗ in Rℓ (H) such that for all p ∈ [m], β ∗ (Qp ) ⊆ β(Sp ). Since β ∗ 4  ′ ′ and β are two χ-colorings of H such that for all p ∈ [m], β ∗ (Qp ) ⊆ β(Sp ) and β (Qp ) ⊆ β(Sp ), ′ by Lemma 2 there is a path between β ∗ and β in Rℓ (H). Therefore, there is a path between ′ ′ α and β in Rℓ (H). Lemma 4. Let G be a graph such that V (G) can be partitioned into maximal modules S1 ,... , Sm. Assume every proper induced subgraph of G is recolorable. Let H = G(Q1 ,... , Qm ) be the ′ ′ clique skeleton of G. Let ℓ ≥ χ(G)+1. Let α and β be two χ-colorings of G. Let α and β ′ ′ be two χ-colorings of H such that for all p ∈ [m], α (Qp ) ⊆ α(Sp ) and β (Qp ) ⊆ β(Sp ). Then ′ there exists a path between α and β in Rℓ (G) if and only if there exists a path between α and ′ β in Rℓ (H). Proof. Assume the hypotheses. First assume that there is a path between α and β in Rℓ (G). Then by Lemma 3, there is a ′ ′ path between α and β in Rℓ (H). ′ ′ Now assume that there is a path between α and β in Rℓ (H). Let α∗ and β ∗ be two χ- ′ ′ colorings of G such that for all p ∈ [m], α∗ (Sp ) = α (Qp ) and β ∗ (Sp ) = β (Qp ). Then since for ′ ′ all p ∈ [m], α (Qp ) ⊆ α(Sp ) and β (Qp ) ⊆ β(Sp ), clearly for all p ∈ [m], α∗ (Sp ) ⊆ α(Sp ) and β ∗ (Sp ) ⊆ β(Sp ). Thus by Lemma 1, there is a path from α to α∗ and there is a path from β to β ∗ in Rℓ (G), for any ℓ ≥ χ(G)+1. We will now prove that there is a path from α∗ to β ∗ in Rℓ (G). ′ ′ ′ ′ Let P be a path between α and β in Rℓ (H). Let αi and αi+1 be two ℓ-colorings of H which ′ are adjacent in P. Let αi be an ℓ-coloring of G such that for all p ∈ [m], αi (Sp ) = αi (Qp ). We prove that there is a path from αi to some ℓ-coloring of G, say αi+1 , in Rℓ (G), such that ′ ′ ′ αi+1 (Sp ) = αi+1 (Qp ), for all p ∈ [m]. Since αi and αi+1 are adjacent in Rℓ (H), they differ on ′ ′ a single vertex. Let v ∈ Qj ⊆ V (H), where αi (v) 6= αi+1 (v). Note that there are no vertices ′ ′ in the closed neighborhood of v colored αi+1 (v) under the coloring αi of H. Thus there are no ′ vertices in the closed neighborhood of any vertex in Sj colored αi+1 (v) under the coloring αi of G. Let αi+1 be an ℓ-coloring of G obtained from αi by recoloring every vertex in Sj colored ′ ′ αi (v) with the color αi+1 (v), one at a time. This corresponds to a path between αi and αi+1 in ′ ′ ′ Rℓ (G), where αi+1 (Sp ) = αi+1 (Qp ) for all p ∈ [m]. Hence, if there is a path between α and β in Rℓ (H), then there is a path from α∗ to some coloring γ in Rℓ (G), such that for all p ∈ [m], ′ γ(Sp ) = β (Qp ). Since β ∗ and γ are two χ-colorings of G such that for all p ∈ [m], β ∗ (Sp ) = γ(Sp ), by Lemma 1, there is a path between β ∗ and γ in Rℓ (G). Therefore, there is a path between α∗ and β ∗ in Rℓ (G). Theorem 6. Let G be a graph such that V (G) can be partitioned into maximal modules S1 ,... , Sm. Let H = G(Q1 ,... , Qm ) be the clique skeleton of G. Let ℓ ≥ χ(G)+1. If every proper induced subgraph of G is recolorable, then Rℓ (G) is connected if and only if Rℓ (H) is connected. Proof. Assume the hypotheses. We first prove that, for any ℓ ≥ χ(G)+1, if Rℓ (G) is connected, then Rℓ (H) is connected. ′ ′ Let α be any ℓ-coloring of H and let β be a χ-coloring of H. Let α be an ℓ-coloring of G and ′ ′ let β be a χ-coloring of G, such that for all p ∈ [m], α(Sp ) = α (Qp ) and β(Sp ) = β (Qp ). Since Rℓ (G) is connected, there is a path between α and β in Rℓ (G). Then by Lemma 3, there is a ′ ′ path between α and β in Rℓ (H). Therefore, Rℓ (H) is connected. We now prove that, for any ℓ ≥ χ(G)+1, if Rℓ (H) is connected, then Rℓ (G) is connected. ′ Note that for each χ-coloring µ of G there is a χ-coloring µ of H such that for all p ∈ [m], ′ ′ µ (Qp ) ⊆ µ(Sp ). Similarly, for each χ-coloring µ of H there is a χ-coloring µ of G such that ′ for all p ∈ [m], µ(Sp ) = µ (Qp ). Hence, if Rℓ (H) is connected, then by Lemma 4, there is a path between any two χ-colorings of G in Rℓ (G). Thus, to prove that Rℓ (G) is connected, it is sufficient to prove that given any ℓ-coloring of G, we can reach a χ-coloring in Rℓ (G). Let α be an ℓ-coloring of G. Since for all p ∈ [m], G[Sp ] is recolorable, recolor the vertices in each Sp , one at a time, to use at most χ(G[Sp ]) colors without changing the colors on vertices 5  ′ in Sj , j 6= p, to obtain a coloring β of G. Let β be an ℓ-coloring of H such that for all p ∈ [m], ′ ′ β (Qp ) = β(Sp ). Let γ be a χ-coloring of H. Since Rℓ (H) is connected, there is a path P ′ ′ ′ ′ between β and γ in Rℓ (H). Let αi and αi+1 be two ℓ-colorings of H which are adjacent in ′ the path P. Let αi be an ℓ-coloring of G such that for all p ∈ [m], αi (Sp ) = αi (Qp ). We prove that there is a path from αi to some ℓ-coloring of G, say αi+1 , in Rℓ (G), such that for ′ ′ ′ all p ∈ [m], αi+1 (Sp ) = αi+1 (Qp ). Since αi and αi+1 are adjacent in Rℓ (H), they differ on a single vertex, say v. Let v ∈ Qj , for some j ∈ [m]. Note that there are no vertices in the closed ′ ′ neighborhood of v colored αi+1 (v) under the coloring αi of H. Thus there are no vertices in the ′ closed neighborhood of any vertex in Sj colored αi+1 (v) under the coloring αi of G. Let αi+1 ′ be an ℓ-coloring of G obtained from αi by recoloring every vertex in Sj colored αi (v), one at a ′ time, with the color αi+1 (v). This corresponds to a path between αi and αi+1 in Rℓ (G), where ′ ′ ′ αi+1 (Sp ) = αi+1 (Qp ) for all p ∈ [m]. Hence, if there is a path from β to γ in Rℓ (H), then we can recolor the vertices of G from any ℓ-coloring α of G to some χ-coloring of G. The results below are well-known, for example see [1, 3]. Lemma 5. If G is a join of two recolorable graphs G1 and G2 , then G is recolorable. Lemma 6. Let G be a graph with non-adjacent vertices u and v, such that N (u) ⊆ N (v). Then either (i) G is recolorable or (ii) G-u is not recolorable. We now prove Theorem 1. Proof of Theorem 1. Let G be a hereditary class of graphs and let H be the set of prime graphs in G. Assume that for all H ∈ H, every blowup of H is recolorable. If possible, let G ∈ G be a vertex-minimal graph that is not recolorable. Then G is neither a join nor a disjoint union of two graphs. Let S1 ,... , Sm be a partition of V (G) into maximal modules. Let G∗ be the skeleton of G. Then G∗ is a prime induced subgraph of G and hence is in H. Since G∗ ∈ H, from the hypothesis, every blowup of G∗ is recolorable. Let H ∗ = G(Q1 ,... , Qm ) be the clique skeleton of G. Note that H ∗ is a blowup of G∗ and hence is recolorable. By the vertex minimality of G, every proper induced subgraph of G is recolorable. Therefore, since H ∗ is recolorable, by Theorem 6, G is recolorable, a contradiction. Let G be a hereditary class of graphs and let H be the set of prime graphs in G. It follows from Theorem 1 that to determine if every G ∈ G is recolorable, it is sufficient to determine if every blowup of every H ∈ H is recolorable. We can further ask: to determine if every G ∈ G is recolorable, is it sufficient to determine if every H ∈ H is recolorable? We answer this in the positive for 2K2 -free graphs. Theorem 7. Let G be a hereditary class of graphs such that every G ∈ G is 2K2 -free. If every prime graph in G is recolorable, then every graph in G is recolorable. Proof. Assume the hypothesis. If possible, let G ∈ G be a vertex-minimal graph that is not recolorable. Then G is not prime. Since G is not prime, it contains a maximal module with at least two vertices, say S. Let u, v ∈ S. If S is an independent set, then N (u) = N (v). Then by Lemma 6, G is not vertex-minimal, a contradiction. So S must contain an edge. Without loss of generality, let uv ∈ E(G). If S is complete to V (G) \ S, then G is a join of G[S] and G-S. Then by Lemma 5, G is not vertex-minimal, a contradiction. Hence there is a vertex x ∈ V (G) \ S that is non-adjacent to some vertex in S. Since S is a module, x is non-adjacent to every vertex in S. If N (x) ⊆ N (v), then by Lemma 6, G is not vertex-minimal, a contradiction. Thus there is a vertex y ∈ N (x) \ N (v). Then y ∈ V (G) \ S since x is non-adjacent to every vertex in S. Since S is a module and y is non-adjacent to v ∈ S, y is non-adjacent to every vertex in S. Then {u, v, x, y} induces a 2K2 , a contradiction. 6 Lemma 7. () Let G contain a vertex v of degree at most χ(G)-1. Then, either (i) G is recolorable or (ii) G-v is not recolorable. Theorem 8. Let G be a hereditary class of graphs such that every G ∈ G is diamond-free. If every prime graph in G is recolorable, then every graph in G is recolorable. Proof. Assume the hypothesis. If possible, let G ∈ G be a vertex-minimal graph that is not recolorable. Then G is connected and not prime. Since G is not prime, it contains a non-trivial module, say S, with at least two vertices. Since G is connected, there exists a vertex z ∈ V (G) \ S adjacent to every vertex in S. If G[S] contains an induced P3 , induced by, say, the set P ⊆ S, then P ∪ {z} induces a diamond in G, a contradiction. So G[S] is P3 -free and hence G[S] is a disjoint union of cliques. If there are adjacent vertices u and v in S, then we claim that N [u] = N [v] is a clique. Since S is a module and a disjoint union of cliques, N [u] = N [v]. If N [u] is not a clique, then there exist two non-adjacent vertices x and y in V (G) \ S adjacent to both u and v, a contradiction to the fact that G is diamond-free. Thus N [u] = N [v] is a clique. Therefore, where d(u) denotes the degree of the vertex u in G, d(u) ≤ ω(G)-1 ≤ χ(G)-1. By vertex minimality of G, the graph G-u must be recolorable. Then by Lemma 7, G is recolorable, a contradiction. If there are no adjacent vertices in S, then S is an independent set in G. Let {u, v} ⊆ S. Since S is a module, N (u) = N (v). By vertex minimality of G, the graph G-u must be recolorable. Then by Lemma 6, G is recolorable, a contradiction. 4 P5 -free graphs In this section, we use the results from previous section to prove recolorability results for several subclasses of P5 -free graphs. A clique cutset Q of a graph G is a clique in G such that G-Q has more components than G. A clique cutset Q of a graph G is called a tight clique cutset if there exists a component H of G-Q which is complete to Q. We use the following results in our proof. Lemma 8. () Suppose G has a tight clique cutset. If every proper induced subgraph of G is recolorable, then G is recolorable. Lemma 9. Every blowup of a 3K1 -free graph is recolorable. Proof. Clearly, every blowup of a 3K1 -free graph is 3K1 -free. Thus the lemma follows from the result proved in that every 3K1 -free graph is recolorable. A graph is said to be chordal if it does not contain an induced cycle of length more than three. Lemma 10. Every blowup of a chordal graph is recolorable. Proof. Clearly, every blowup of a chordal graph is chordal. Thus the lemma follows from the result proved in that every chordal graph is recolorable. Lemma 11. Every blowup of a prime graph with at most 5 vertices is recolorable. Proof. Let G be any prime graph with at most 5 vertices. If G is (P5 , C4 )-free, then every blowup of G is (P5 , C4 )-free. Thus the lemma follows from the result proved in that every (P5 , C4 )-free graph is recolorable. Note that there are no prime graphs with at most 4 vertices containing an induced P5 or an induced C4. The only 5-vertex prime graphs containing an induced P5 or an induced C4 are P5 and the house. If G is the house, then since the house is 3K1 -free, the result follows from Lemma 9. If G is P5 , then since P5 is chordal, the result follows from Lemma 10. 7  Two edges in a graph are said to be independent if they do not share an end vertex. A matching is a set of mutually independent edges. A matched co-bipartite graph is the com- plement of Kp,q -M , where M is a maximum matching, for some p, q ≥ 1. Note that every matched co-bipartite graph is a co-bipartite graph. We use the modular decomposition of (P5 , diamond)-free graphs given by Brandstädt to prove that every (P5 , diamond)-free graph is recolorable. Theorem 9. () If G is a prime (P5 , diamond)-free graph containing a 2K2 , then G is a matched co-bipartite graph. Theorem 10. () Every (2K2 , diamond)-free graph is recolorable. We now have all the ingredients to prove Theorem 2. Proof of Theorem 2. By Theorem 8, it is sufficient to prove that every prime (P5 , diamond)-free graph is recolorable. Let G be a prime (P5 , diamond)-free graph. If G is 2K2 -free, then the result follows from Theorem 10. If G contains a 2K2 , then by Theorem 9, G is a matched co-bipartite graph. Since matched co-bipartite graphs are 3K1 -free, by Lemma 9, G is recolorable. Lemma 12. () Let G = (V , E) be a prime graph on n vertices. Then G is bipartite and P5 -free if and only if the following conditions hold: There exists a partition of V (G) into two independent sets B = {b1 , b2 ,... , b n2 } and W = {w1 , w2 ,... , w n2 }. The neighbors of bi (i = 1,... , n2 ) are precisely w1 ,... , w n2 −i+1. Lemma 13. Every blowup of a prime P5 -free bipartite graph is recolorable. Proof. If possible, let H be a vertex-minimal minimal counter example, say H is a blowup of some prime P5 -free bipartite graph G. By Lemma 12, G has a vertex of degree 1. The neighbor of this degree 1 vertex is a tight clique cutset of G. Thus H has a tight clique cutset. Every proper induced subgraph of H is also a blowup of some prime P5 -free bipartite graph and hence recolorable. Then by Lemma 8, H is recolorable, a contradiction. Lemma 14. Every blowup of a co-bipartite graph is recolorable. Proof. Clearly, every co-bipartite graph is 3K1 -free. Hence the result follows from Lemma 9. Theorem 11. () If G is a prime (P5 , house, bull)-free graph on 6 or more vertices without a universal vertex, then G is either a bipartite graph or a co-bipartite graph. We now prove Theorem 3. Proof of Theorem 3. By Theorem 1, it is sufficient to prove that every blowup of every prime (P5 , house, bull)-free graph is recolorable. Let G be a prime (P5 , house, bull)-free graph. By Lemma 5, we may assume that G does not have a universal vertex. By Lemma 11, we may assume that G has at least 6 vertices. By Theorem 11, G is a bipartite graph or a co-bipartite graph. Then the result follows from Lemma 13 and Lemma 14. A thin spider is a graph whose vertex set can be decomposed into a clique K and an independent set S, such that |K| = |S| or |K| = |S|+1, and the edges between S and K form a matching, leaving at most one vertex of K with no neighbor in S. Lemma 15. Every blowup of a thin spider or the complement of a thin spider is recolorable. 8 Proof. Let H be a blowup of a thin spider or the complement of a thin spider. Since every thin spider and every complement of a thin spider is chordal, the graph H is recolorable by Lemma 10. Theorem 12. () Let G be a prime semi-P4 -sparse graph. Then either G or its complement is a bipartite graph or a thin spider. We now prove Theorem 4. Proof of Theorem 4. By Theorem 1, it is sufficient to prove that every blowup of every prime semi-P4 -sparse graph is recolorable. Let G be a prime semi-P4 -sparse graph. Note that G is P5 -free. By Theorem 12, G or its complement is a bipartite graph or a thin spider. If G or its complement is a bipartite graph, then the result follows from Lemma 13 or Lemma 14, respectively. If G or its complement is a thin spider, then the result follows from Lemma 15. Theorem 13. () Every prime (P5 , house)-free graph is either a C5 or C5 -free. We now prove Theorem 5. Proof of Theorem 5. It is obvious that if every (P5 , house)-free graph is recolorable, then every (P5 , house, C5 )-free graph is recolorable. Now assume that every (P5 , house, C5 )-free graph is recolorable. By Theorem 1, it is sufficient to prove that every blowup of every prime (P5 , house)-free graph is recolorable. Let G be a prime (P5 , house)-free graph. If G is C5 -free, then every blowup of G is (P5 , house, C5 )-free and hence recolorable. If G contains a C5 , then by Theorem 13, G is isomorphic to C5. Since C5 is 3K1 -free, every blowup of C5 is recolorable by Lemma 9. 5 Conclusion Let G be a hereditary class of graphs. In Theorem 1, we proved that every graph in G is recol- orable if every blowup of every prime graph in G is recolorable. We have two questions. 1 5 3 6 4 1 2 2 1 4 6 3 5 ′ Figure 2: A graph G (left) and a blowup G of it (right). Question 1 : If every prime graph in G is recolorable, then is every graph in G recolorable? We answered Question 1 positively for 2K2 -free graphs and would like to know if it is true in general. Furthermore, we can ask if every blowup of a prime recolorable graph recolorable. We answer this in the negative. 9  It is easy to see that the graph G in Figure 2 (left) is a prime 3-chromatic graph and it ′ ′ is recolorable, but the blowup G of G (right) is 5-chromatic and R6 (G ) is disconnected and ′ hence G is not recolorable. However, we can see that G has a prime induced subgraph, C6 , which is not recolorable. We conjecture the following: Conjecture 1. Let G be a prime graph. Every blowup of G is recolorable if and only if every induced subgraph of G is recolorable. Acknowledgement We thank Chı́nh T. Hoàng for helpful suggestions. References M. Belavadi and K. Cameron. Recoloring some hereditary graph classes. Available at https://arxiv.org/abs/2312.00979, 2024. M. Belavadi, K. Cameron, and O. Merkel. Reconfiguration of vertex colouring and forbidden induced subgraphs. European Journal of Combinatorics 118, paper no. 103908, 2024. T. Biedl, A. Lubiw, and O. Merkel. Building a larger class of graphs for efficient reconfigura- tion of vertex colouring. In J. Nešetřil, G. Perarnau, J. Rué, and O. Serra, editors, Extended Abstracts EuroComb 2021, pages 286–292, Cham, 2021. Springer International Publishing. M. Bonamy and N. Bousquet. Recoloring graphs via tree decompositions. European Journal of Combinatorics 69, 200–213, 2018. M. Bonamy, M. Johnson, I. Lignos, V. Patel, and D. Paulusma. Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization 27, 132–143, 2014. P. Bonsma and L. Cereceda. Finding paths between graph colourings: PSPACE- completeness and superpolynomial distances. Theoretical Computer Science 410, 5215–5226, 2009. A. Brandstädt. (P5 , diamond)-free graphs revisited: structure and linear time optimization. Discrete Applied Mathematics 138, 13–27, 2004. L. Cereceda, J. van den Heuvel, and M. Johnson. Finding paths between 3-colourings. Proceedings of the 19th International Workshop on Combinatorial Algorithms, IWOCA, 182- –196, 2008. D. Corneil, M. Habib, C. Paul, and M. Tedder. A recursive linear time modular decompo- sition algorithm via LexBFS. Available at https://arxiv.org/abs/0710.3901, 2024. C. Feghali and J. Fiala. Reconfiguration graph for vertex colourings of weakly chordal graphs. Discrete Mathematics 343(3), paper no. 111733, 2020. C. Feghali and O. Merkel. Mixing colourings in 2K2 -free graphs. Discrete Mathematics 345(11), paper no. 113108, 2022. J. L. Fouquet. A decomposition for a class of (P5 , P5 )-free graphs. Discrete Mathematics 121, 75–83, 1993. 10  J. L. Fouquet and V. Giakoumakis. On semi-P4 -sparse graphs. Discrete Mathematics 165/166, 277–300, 1997. J. L. Fouquet and J. M. Vanherpe. Seidel complementation on (P5 , house, bull)-free graphs. Available at https://arxiv.org/abs/1003.5458, 2010. Chı́nh T. Hoàng. On the structure of (banner, odd hole)-free graphs. Journal of Graph Theory 89, 395–412, 2018. B. Jamison and S. Olariu. A tree representation for P4 -sparse graphs. Discrete Applied Mathematics 35, 115–129, 1992. O. Merkel. Recolouring weakly chordal graphs and the complement of triangle-free graphs. Discrete Mathematics 345, paper no. 112708, 2022. M. Wrochna. Reconfiguration in bounded bandwidth and tree-depth. Journal of Computer and System Sciences 93, 1–10, 2018. 11