Search

Let G be a bridgeless cubic graph. The Berge–Fulkerson Conjecture (1970s) states that G admits a list of six perfect matchings such that each edge of G belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan–Raspaud Conjecture (1994), which states that G admits three perfect matchings such that every edge of G belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that G admits two perfect matchings whose deletion yields a bipartite subgraph of G. It can be shown that given an arbitrary perfect matching of G , it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan–Raspaud and the Berge–Fulkerson conjectures, respectively. In this paper, we show that given any 1 + -factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G , there always exists a perfect matching M of G containing e such that G ∖ (F ∪ M) is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in G , there exists a perfect matching of G containing at least one edge of each circuit in this collection. [ABSTRACT FROM AUTHOR]

Let k and d be positive integers such that k ≥ d + 2. Consider two k -colourings of a d -degenerate graph G. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper colouring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda conjectured that there should exist one of quadratic length. The k -reconfiguration graph of G is the graph whose vertices are the proper k -colourings of G , with an edge between two colourings if they differ on exactly one vertex. Cereceda's conjecture can be reformulated as follows: the diameter of the (d + 2) -reconfiguration graph of any d -degenerate graph on n vertices is O (n 2). So far, there is no proof of a polynomial upper bound on the diameter, even for d = 2. In this paper, we prove that the diameter of the k -reconfiguration graph of a d -degenerate graph is O (n d + 1) for k ≥ d + 2. Moreover, we prove that if k ≥ 3 2 (d + 1) then the diameter of the k -reconfiguration graph is quadratic, improving the previous bound of k ≥ 2 d + 1. We also show that the 5-reconfiguration graph of planar bipartite graphs has quadratic diameter, confirming Cereceda's conjecture for this class of graphs. [ABSTRACT FROM AUTHOR]

The canonical double cover B (X) of a graph X is the direct product of X and K 2. If Aut (B (X)) ≅ Aut (X) × Z 2 then X is called stable; otherwise X is called unstable. An unstable graph is nontrivially unstable if it is connected, non-bipartite and distinct vertices have different neighborhoods. A circulant is a Cayley graph on a cyclic group. Qin et al. (2019) [18] conjectured that there are no nontrivially unstable circulants of odd order. In this paper we prove this conjecture. [ABSTRACT FROM AUTHOR]

An edge cut C of a graph G is tight if | C ∩ M | = 1 for every perfect matching M of G. Barrier cuts and 2-separation cuts are called ELP-cuts , which are two important types of tight cuts in matching covered graphs. Edmonds, Lovász and Pulleyblank proved that if a matching covered graph has a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho, Lucchesi, and Murty made a stronger conjecture: given any nontrivial tight cut C in a matching covered graph G , there exists a nontrivial ELP-cut D in G which does not cross C. We confirm the conjecture in this paper. [ABSTRACT FROM AUTHOR]

The extremal number ex (n , F) of a graph F is the maximum number of edges in an n -vertex graph not containing F as a subgraph. A real number r ∈ [ 1 , 2 ] is realisable if there exists a graph F with ex (n , F) = Θ (n r). Several decades ago, Erdős and Simonovits conjectured that every rational number in [ 1 , 2 ] is realisable. Despite decades of effort, the only known realisable numbers are 0 , 1 , 7 5 , 2 , and the numbers of the form 1 + 1 m , 2 − 1 m , 2 − 2 m for integers m ≥ 1. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than the two numbers 1 and 2. In this paper, we make progress on the conjecture of Erdős and Simonovits. First, we show that 2 − a b is realisable for any integers a , b ≥ 1 with b > a and b ≡ ± 1 (mod a). This includes all previously known ones, and gives infinitely many limit points 2 − 1 m in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable. [ABSTRACT FROM AUTHOR]