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 Γ be a connected (X , 2) -arc-transitive bipartite graph with bi-parts Δ 0 and Δ 1 , where X ≤ Aut (Γ). Let X + be the subgroup of X fixing Δ 0 setwise. In this paper, we first prove that if X + is primitive and faithful on Δ 0 and Δ 1 , then the actions of X + on Δ 0 and Δ 1 are primitive of the same type X with X ∈ { HA , SA , PA }. This is then used to prove that if X + is quasiprimitive on Δ 0 of type HA or TW, then either soc (X +) ⊴ Aut (Γ) , or Γ ≅ K q , q (q a prime power) or Γ ≅ K 2 r , 2 r − 2 r K 2 (r ≥ 2). This confirms a conjecture of C. H. Li from 2008. [ABSTRACT FROM AUTHOR]

Many conjectures and open problems in graph theory can either be reduced to cubic graphs or are directly stated for them. Furthermore, it is known that for a lot of problems, a counterexample must be a snark, that is, a bridgeless cubic graph which is not 3-edge-colourable. In this paper we deal with the fact that the family of potential counterexamples to many interesting conjectures can be narrowed even further to the family S ≥ 5 of bridgeless cubic graphs whose edge set cannot be covered with four perfect matchings. The Cycle Double Cover Conjecture, the Shortest Cycle Cover Conjecture and the Fan–Raspaud Conjecture are examples of statements for which S ≥ 5 is crucial. In this paper we study parameters which have the potential to further refine S ≥ 5 and thus enlarge the set of cubic graphs for which the mentioned conjectures can be verified. We show that S ≥ 5 can be naturally decomposed into subsets with increasing complexity, thereby producing a natural scale for proving these conjectures. More precisely, we consider the following parameters and questions: given a bridgeless cubic graph, (i) how many perfect matchings need to be added, (ii) how many copies of the same perfect matching need to be added, and (iii) how many 2-factors need to be added so that the resulting regular graph is Class I? We present new results for these parameters and we also establish some strong relations between these problems and some long-standing conjectures. [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]

A family F of sets is union-closed if the union of any two sets from F belongs to F. The union-closed sets conjecture states that if F is a finite union-closed family of finite sets, then there is an element that belongs to at least half of the sets in F. The conjecture has several equivalent formulations in terms of other combinatorial structures such as lattices and graphs. In its whole generality the conjecture remains wide open, but it was verified for various important classes of lattices, such as lower semimodular lattices, and graphs, such as chordal bipartite graphs. In the present paper we develop a Boolean approach to the conjecture and verify it for several classes of Boolean functions, such as submodular functions and double Horn functions. [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]

The reconfiguration graph C k (G) for the k -colourings of a graph G has a vertex for each proper k -colouring of G , and two vertices of C k (G) are adjacent precisely when those k -colourings differ on a single vertex of G. Much work has focused on bounding the maximum value of diam C k (G) over all n -vertex graphs G. We consider the analogous problems for list colourings and for correspondence colourings. We conjecture that if L is a list-assignment for a graph G with | L (v) | ≥ d (v) + 2 for all v ∈ V (G) , then diam C L (G) ≤ n (G) + μ (G). We also conjecture that if (L , H) is a correspondence cover for a graph G with | L (v) | ≥ d (v) + 2 for all v ∈ V (G) , then diam C (L , H) (G) ≤ n (G) + τ (G). (Here μ (G) and τ (G) denote the matching number and vertex cover number of G.) For every graph G , we give constructions showing that both conjectures are best possible, which also hints towards an exact form of Cereceda's Conjecture for regular graphs. Our first main result proves the upper bounds (for the list and correspondence versions, respectively) diam C L (G) ≤ n (G) + 2 μ (G) and diam C (L , H) (G) ≤ n (G) + 2 τ (G). Our second main result proves that both conjectured bounds hold, whenever all v satisfy | L (v) | ≥ 2 d (v) + 1. We conclude by proving one or both conjectures for various classes of graphs such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with bounded maximum average degree. The full paper can also be found at arxiv.org/abs/2204.07928. [ABSTRACT FROM AUTHOR]

Ryser's Conjecture states that any r -partite r -uniform hypergraph has a vertex cover of size at most r − 1 times the size of the largest matching. For r = 2 , the conjecture is simply König's Theorem and every bipartite graph is a witness for its tightness. The conjecture has also been proven for r = 3 by Aharoni using topological methods, but the proof does not give information on the extremal 3-uniform hypergraphs. Our goal in this paper is to characterize those hypergraphs which are tight for Aharoni's Theorem. Our proof of this characterization is also based on topological machinery, particularly utilizing results on the (topological) connectedness of the independence complex of the line graph of the link graphs of 3-uniform Ryser-extremal hypergraphs. We use this information to nail down the elements of a structure we call home-base hypergraph . While there is a single minimal home-base hypergraph with matching number k for every positive integer k ∈ N , home-base hypergraphs with matching number k are far from being unique. There are infinitely many of them and each of them is composed of k copies of two different kinds of basic structures, whose hyperedges can intersect in various restricted, but intricate ways. Our characterization also proves an old and wide open strengthening of Ryser's Conjecture, due to Lovász, for the 3-uniform extremal case, that is, for hypergraphs with τ = 2 ν . [ABSTRACT FROM AUTHOR]

For graphs H and F with chromatic number χ (F) = k , we call H strictly F -Turán-good (or (H , F) strictly Turán-good) if the Turán graph T k − 1 (n) is the unique F -free graph on n vertices containing the largest number of copies of H when n is large enough. Let F be a graph with chromatic number χ (F) ≥ 3 and a color-critical edge and let P ℓ be a path with ℓ vertices. Gerbner and Palmer (2020) showed that (P 3 , F) is strictly Turán good if χ (F) ≥ 4 and they conjectured that (a) this result is true when χ (F) = 3 , and, moreover, (b) (P ℓ , K k) is Turán-good for every pair of integers ℓ and k. In the present paper, we show that (H , F) is strictly Turán-good when H is a bipartite graph with matching number ν (H) = ⌊ | V (H) | 2 ⌋ and χ (F) = 3 , as a corollary, this result confirms the conjecture (a); we also prove that (P ℓ , F) is strictly Turán-good for 2 ≤ ℓ ≤ 6 and χ (F) ≥ 4 , this also confirms the conjecture (b) for 2 ≤ ℓ ≤ 6 and k ≥ 4. [ABSTRACT FROM AUTHOR]

Drisko (1998) proved (essentially) that every family of 2 n − 1 matchings of size n in a bipartite graph possesses a partial rainbow matching of size n . In Barát et al. (2017) this was generalized as follows: Any ⌊ k + 2 k + 1 n ⌋ − ( k + 1 ) matchings of size n in a bipartite graph have a rainbow matching of size n − k . The paper has a twofold aim: (i) to extend these results to matchings of not necessarily equal cardinalities, and (ii) to prove a conjecture of Drisko, on the characterization of those families of 2 n − 2 matchings of size n in a bipartite graph that do not possess a rainbow matching of size n . Combining the latter with an idea of Alon (2011), we re-prove a characterization of the extreme case in a well-known theorem of Erdős–Ginzburg–Ziv in additive number theory. [ABSTRACT FROM AUTHOR]

A connected graph G of even order v is called t -extendable if it contains a perfect matching, t < v / 2 and any matching of t edges is contained in some perfect matching. The extendability of G is the maximum t such that G is t -extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is 1 -extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions. In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter D ≥ 3 are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency k ≥ 3 that depend on k , λ and μ , where λ is the number of common neighbors of any two adjacent vertices and μ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency k grows linearly in k . We conjecture that the extendability of a distance-regular graph of even order and valency k is at least ⌈ k / 2 ⌉ − 1 and we prove this fact for bipartite distance-regular graphs. In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters. [ABSTRACT FROM AUTHOR]

A graph Γ is said to be distance-balanced if for any edge u v of Γ , the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u , and it is called nicely distance-balanced if in addition this number is independent of the chosen edge u v. A graph Γ is said to be strongly distance-balanced if for any edge u v of Γ and any integer k , the number of vertices at distance k from u and at distance k + 1 from v is equal to the number of vertices at distance k + 1 from u and at distance k from v. In this paper we solve an open problem posed by Kutnar and Miklavič (2014) by constructing several infinite families of nonbipartite nicely distance-balanced graphs which are not strongly distance-balanced. We disprove a conjecture regarding characterization of strongly distance-balanced graphs posed by Balakrishnan et al. (2009) by providing infinitely many counterexamples, and answer a question posed by Kutnar et al. in (2006) regarding the existence of semisymmetric distance-balanced graphs which are not strongly distance-balanced by providing an infinite family of such examples. We also show that for a graph Γ with n vertices and m edges it can be checked in O (m n) time if Γ is strongly-distance balanced and if Γ is nicely distance-balanced. [ABSTRACT FROM AUTHOR]