Search

A family of sets is intersecting if any two sets in the family intersect. Given a graph G and an integer r ≥ 1 , let I (r) (G) denote the family of independent sets of size r of G. For a vertex v of G , the family of independent sets of size r that contain v is called an r -star. Then G is said to be r -EKR if no intersecting subfamily of I (r) (G) is bigger than the largest r -star. Let n be a positive integer, and let G consist of the disjoint union of n paths each of length 2. We prove that if 1 ≤ r ≤ n ∕ 2 , then G is r -EKR. This affirms a longstanding conjecture of Holroyd and Talbot for this class of graphs and can be seen as an analogue of a well-known theorem on signed sets, proved using different methods, by Deza and Frankl and by Bollobás and Leader. Our main approach is a novel probabilistic extension of Katona's elegant cycle method, which might be of independent interest. [ABSTRACT FROM AUTHOR]

The reconfiguration graph R k (G) of the k -colourings of a graph G contains as its vertex set the k -colourings of G and two colourings are joined by an edge if they differ in colour on just one vertex of G. Bonamy et al. (2014) have shown that if G is a k -colourable chordal graph on n vertices, then R k + 1 (G) has diameter O (n 2) , and asked whether the same statement holds for k -colourable perfect graphs. This was answered negatively by Bonamy and Bousquet (2014). In this note, we address this question for k -colourable weakly chordal graphs, a well-known class of graphs that falls between chordal graphs and perfect graphs. We show that for each k ≥ 3 there is a k -colourable weakly chordal graph G such that R k + 1 (G) is disconnected. On the positive side, we introduce a subclass of k -colourable weakly chordal graphs which we call k -colourable compact graphs and show that for each k -colourable compact graph G on n vertices, R k + 1 (G) has diameter O (n 2). We show that this class contains all k -colourable co-chordal graphs and when k = 3 all 3-colourable (P 5 , P 5 ¯ , C 5) -free graphs. We also mention some open problems. [ABSTRACT FROM AUTHOR]

A decomposition of a multigraph G is a partition of its edges into subgraphs G (1) , ... , G (k). It is called an r -factorization if every G (i) is r -regular and spanning. If G is a subgraph of H , a decomposition of G is said to be enclosed in a decomposition of H if, for every 1 ≤ i ≤ k , G (i) is a subgraph of H (i). Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of λ K n to be enclosed in some 2-edge-connected r -factorization of μ K m for some range of values for the parameters n , m , λ , μ , r : r = 2 , μ > λ and either m ≥ 2 n − 1 , or m = 2 n − 2 and μ = 2 and λ = 1 , or n = 3 and m = 4. We generalize their result to every r ≥ 2 and m ≥ 2 n − 2. We also give some sufficient conditions for enclosing a given decomposition of λ K n in some 2-edge-connected r -factorization of μ K m for every r ≥ 3 and m > (2 − C) n , where C is a constant that depends only on r , λ and μ. [ABSTRACT FROM AUTHOR]