On Cubic Bridgeless Graphs Whose Edge‐Set Cannot be Covered by Four Perfect Matchings

The problem of establishing the number of perfect matchings necessary to cover the edge‐set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this article, we prove that deciding whether this number is at most four for a given cubic bridgeless graph is NP‐complete. We also construct an infinite family of snarks (cyclically 4‐edge‐connected cubic graphs of girth at least 5 and chromatic index 4) whose edge‐set cannot be covered by four perfect matchings. Only two such graphs were known. It turns out that the family also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with m edges has length at least , and we show that this inequality is strict for graphs of . We also construct the first known snark with no cycle cover of length less than .     

Perfect Matchings of Regular Bipartite Graphs

Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges.     

1‐Factor and Cycle Covers of Cubic Graphs

Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest over all lists of k 1‐factors of G. Any list of three 1‐factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge‐covers and for the existence of three 1‐factors with empty intersection. Furthermore, if , then is an upper bound for the girth of G. We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with have a 4‐cycle cover of length and a 5‐cycle double cover. These graphs also satisfy two conjectures of Zhang 18 . We also give a negative answer to a problem stated in 18 .     

Partial Degree Conditions and Cycle Coverings

Let G be a graph of order n. Let W be a subset of with , where k is a positive integer. We show that if for each , then G contains k vertex‐disjoint cycles covering W such that each of the k cycles contains at least three vertices of W.     

Flows and Bisections in Cubic Graphs

A k‐weak bisection of a cubic graph G is a partition of the vertex‐set of G into two parts V₁ and V₂ of equal size, such that each connected component of the subgraph of G induced by () is a tree of at most vertices. This notion can be viewed as a relaxed version of nowhere‐zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere‐zero r‐flow has a ‐weak bisection. In this article, we study problems related to the existence of k‐weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4‐weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5‐weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5‐flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.     

A note on shortest cycle covers of cubic graphs

Let SCC₃(G) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph G. It is proved in this note that if G contains no circuit of length 5 (an improvement of Jackson's (JCTB 1994) result: if G has girth at least 7) and if all 5‐circuits of G are disjoint (a new upper bound of SCC₃(G) for the special class of graphs).     

Perfect Graphs with No Balanced Skew‐Partition are 2‐Clique‐Colorable

A graph G is perfect if for all induced subgraphs H of G, . A graph G is Berge if neither G nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew‐partition.” A clique‐coloring of a graph G is an assignment of colors to the vertices of G in such a way that no inclusion‐wise maximal clique of G of size at least two is monochromatic, and the clique‐chromatic number of G, denoted by , is the smallest number of colors needed to clique‐color G. There exist graphs of arbitrarily large clique‐chromatic number, but it is not known whether the clique‐chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew‐partition is 2‐clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. ( http://arxiv.org/abs/1308.6444 ).     

Local Clique Covering of Claw‐Free Graphs

A clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well‐known problems are discussed. In particular, it is proved that the local clique cover number of every claw‐free graph is at most , where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw‐free graph on n vertices with the minimum degree δ, is at most , where c is a constant.     

On the Complexity of Computing the Excessive [B]‐Index of a Graph

Let B be a positive integer and let G be a simple graph. An excessive [B]‐factorization of G is a minimum set of matchings, each of size B, whose union is . The number of matchings in an excessive [B]‐factorization of G (or ∞ if an excessive [B]‐factorization does not exist) is a graph parameter called the excessive [B]‐index of G and denoted by . In this article we prove that, for any fixed value of B, the parameter can be computed in polynomial time in the size of the graph G. This solves a problem posed by one of the authors at the 21st British Combinatorial Conference.     

Uniquely Cycle‐Saturated Graphs

Given a graph F, a graph G is uniquely F‐saturated if F is not a subgraph of G and adding any edge of the complement to G completes exactly one copy of F. In this article, we study uniquely ‐saturated graphs. We prove the following: (1) a graph is uniquely C₅‐saturated if and only if it is a friendship graph. (2) There are no uniquely C₆‐saturated graphs or uniquely C₇‐saturated graphs. (3) For , there are only finitely many uniquely ‐saturated graphs (we conjecture that in fact there are none). Additionally, our results show that there are finitely many k‐friendship graphs (as defined by Kotzig) for .     

Petersen Cores and the Oddness of Cubic Graphs

Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest over all lists of k 1‐factors of G. We study lists by three 1‐factors, and call with a ‐core of G. If G is not 3‐edge‐colorable, then . In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if , then is an upper bound for the girth of G. We show that bounds the oddness of G as well. We prove that . If , then every ‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with . On the other hand, the difference between and can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer , there exists a bridgeless cubic graph G such that .     

Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles

If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles.     

Vizing's 2‐Factor Conjecture Involving Large Maximum Degree

Let G be an n‐vertex simple graph, and let and denote the maximum degree and chromatic index of G, respectively. Vizing proved that or . Define G to be Δ‐critical if and for every proper subgraph H of G. In 1965, Vizing conjectured that if G is an n‐vertex Δ‐critical graph, then G has a 2‐factor. Luo and Zhao showed if G is an n‐vertex Δ‐critical graph with , then G has a hamiltonian cycle, and so G has a 2‐factor. In this article, we show that if G is an n‐vertex Δ‐critical graph with , then G has a 2‐factor.     

Strong Circuit Double Cover of Some Cubic Graphs

Let C be a given circuit of a bridgeless cubic graph G. It was conjectured by Seymour that G has a circuit double cover (CDC) containing the given circuit C. This conjecture (strong CDC [SCDC] conjecture) has been verified by Fleischner and Häggkvist for various families of graphs and circuits. In this article, some of these earlier results have been improved: (1) if contains a Hamilton path or a Y‐tree of order less than 14, then G has a CDC containing C; (2) if is connected and , then G has a CDC containing C.     

Maximal Induced Matchings in Triangle‐Free Graphs

An induced matching in a graph is a set of edges whose endpoints induce a 1‐regular subgraph. It is known that every n‐vertex graph has at most  maximal induced matchings, and this bound is the best possible. We prove that every n‐vertex triangle‐free graph has at most  maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K_{3, 3}. Our result implies that all maximal induced matchings in an n‐vertex triangle‐free graph can be listed in time , yielding the fastest known algorithm for finding a maximum induced matching in a triangle‐free graph.     

Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum‐size matching and it is factor critical if has a perfect matching for each vertex v of G. It is known that any 2‐connected equimatchable graph is either bipartite or factor critical. We prove that for 2‐connected factor‐critical equimatchable graph G the graph is either or for some n for any vertex v of G and any minimal matching M such that is a component of . We use this result to improve the upper bounds on the maximum number of vertices of 2‐connected equimatchable factor‐critical graphs embeddable in the orientable surface of genus g to if and to if . Moreover, for any nonnegative integer g we construct a 2‐connected equimatchable factor‐critical graph with genus g and more than vertices, which establishes that the maximum size of such graphs is . Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers g, h, and k we provide a construction of arbitrarily large 2‐connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face‐width k. Finally, we prove that any d‐degenerate 2‐connected equimatchable factor‐critical graph has at most vertices, where a graph is d‐degenerate if every its induced subgraph contains a vertex of degree at most d.     

The decycling number and maximum genus of cubic graphs

Let and denote the minimum size of a decycling set and maximum genus of a graph G, respectively. For a connected cubic graph G of order n, it is shown that . Applying the formula, we obtain some new results on the decycling number and maximum genus of cubic graphs. Furthermore, it is shown that the number of vertices of a decycling set S in a k‐regular graph G is , where c and are the number of components of and the number of edges in , respectively. Therefore, S is minimum if and only if is minimum. As an application, this leads to a lower bound for of a k‐regular graph G. In many cases this bound may be sharp.     

Graph operations and upper bounds on graph homomorphism counts

We construct a family of countexamples to a conjecture of Galvin [5], which stated that for any n‐vertex, d‐regular graph G and any graph H (possibly with loops), where is the number of homomorphisms from G to H. By exploiting properties of the graph tensor product and graph exponentiation, we also find new infinite families of H for which the bound stated above on holds for all n‐vertex, d‐regular G. In particular, we show that if H_WR is the complete looped path on three vertices, also known as the Widom–Rowlinson graph, then for all n‐vertex, d‐regular G. This verifies a conjecture of Galvin.     

More on foxes

An edge in a k‐connected graph G is called k‐contractible if the graph obtained from G by contracting e is k‐connected. Generalizing earlier results on 3‐contractible edges in spanning trees of 3‐connected graphs, we prove that (except for the graphs if ) (a) every spanning tree of a k‐connected triangle free graph has two k‐contractible edges, (b) every spanning tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (c) for , every DFS tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (d) every spanning tree of a cubic 3‐connected graph nonisomorphic to K₄ has at least many 3‐contractible edges, and (e) every DFS tree of a 3‐connected graph nonisomorphic to K₄, the prism, or the prism plus a single edge has two 3‐contractible edges. We also discuss in which sense these theorems are best possible.     

Strong Chromatic Index of Sparse Graphs

A coloring of the edges of a graph G is strong if each color class is an induced matching of G. The strong chromatic index of G, denoted by , is the least number of colors in a strong edge coloring of G. Chang and Narayanan (J Graph Theory 73(2) (2013), 119–126) proved recently that for a 2‐degenerate graph G. They also conjectured that for any k‐degenerate graph G there is a linear bound , where c is an absolute constant. This conjecture is confirmed by the following three papers: in (G. Yu, Graphs Combin 31 (2015), 1815–1818), Yu showed that . In (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), D?bski, Grytczuk, and ?leszyńska‐Nowak showed that . In (T. Wang, Discrete Math 330(6) (2014), 17–19), Wang proved that . If G is a partial k‐tree, in (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), it is proven that . Let be the line graph of a graph G, and let be the square of the line graph . Then . We prove that if a graph G has an orientation with maximum out‐degree k, then has coloring number at most . If G is a k‐tree, then has coloring number at most . As a consequence, a graph with has , and a k‐tree G has .