On Coloring Problems of Snark Families

Snarks are cubic bridgeless graphs of chromatic index 4 which had their origin in the search of counterexamples to the Four Color Theorem. In 2003, Cavicchioli et al. proved that for snarks with less than 30 vertices, the total chromatic number is 4, and proposed the problem of finding (if any) the smallest snark which is not 4-total colorable. Since then, only two families of snarks have had their total chromatic number determined to be 4, namely the Flower Snark family and the Goldberg family.We prove that the total chromatic number of the Loupekhine family is 4. We study the dot product, a known operation to construct snarks. We consider families of snarks using the dot product, particularly subfamilies of the Blanusa families, and obtain a 4-total coloring for each family. We study edge coloring properties of girth trivial snarks that cannot be extended to total coloring. We classify the snark recognition problem as CoNP-complete and establish that the chromatic number of a snark is 3.     

Decomposition of snarks

There are several methods for constructing snarks (cubic graphs with chromatic index 4). We study the reverse process of splitting a snark into smaller snarks which compose it. We also introduce the notion of a “prime” snark.     

Cayley Snarks and Almost Simple Groups

A Cayley snark is a cubic Cayley graph which is not 3-edge-colourable. In the paper we discuss the problem of the existence of Cayley snarks. This problem is closely related to the problem of the existence of non-hamiltonian Cayley graphs and to the question whether every Cayley graph admits a nowhere-zero 4-flow. So far, no Cayley snarks have been found. On the other hand, we prove that the smallest example of a Cayley snark, if it exists, comes either from a non-abelian simple group or from a group which has a single non-trivial proper normal subgroup. The subgroup must have index two and must be either non-abelian simple or the direct product of two isomorphic non-abelian simple groups. Received January 18, 2000 Research partially supported by VEGA grant 1/3213/96 Research partially supported by VEGA grants 1/3213/96 and 1/4318/97     

A survey on snarks and new results: Products,reducibility and a computer search

In this paper we survey recent results and problems of both theoretical and algorithmic character on the construction of snarks—non-trivial cubic graphs of class two, of cyclic edge-connectivity at least 4 and with girth ≥ 5. We next study the process, also considered by Cameron, Chetwynd, Watkins, Isaacs, Nedela, and Sˇkoviera, of splitting a snark into smaller snarks which compose it. This motivates an attempt to classify snarks by recognizing irreducible and prime snarks and proving that all snarks can be constructed from them. As a consequence of these splitting operations, it follows that any snark (other than the Petersen graph) of order ≤ 26 can be built as either a dot product or a square product of two smaller snarks. Using a new computer algorithm we have confirmed the computations of Brinkmann and Steffen on the classification of all snarks of order less than 30. Our results recover the well-known classification of snarks of order not exceeding 22. Finally, we prove that any snark G of order ≤ 26 is almost Hamiltonian, in the sense that G has at least one vertex v for which G \ v is Hamiltonian. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 57–86, 1998     

Special Classes of Snarks

We report the most relevant results on the classification, up to isomorphism, of nontrivial simple uncolorable (i.e., the chromatic index equals 4) cubic graphs, called snarks in the literature. Then we study many classes of snarks satisfying certain additional conditions, and investigate the relationships among them. Finally, we discuss connections between the snark family and some significant conjectures of graph theory, and list some problems and open questions which arise naturally in this research.     

Infinite Classes of Dihedral Snarks

Flower snarks and Goldberg snarks are two infinite families of cyclically 5–edge–connected cubic graphs with girth at least five and chromatic index four. For any odd integer k, k > 3, there is a Flower snark, say J _k , of order 4k and a Goldberg snark, say B _k , of order 8k. We determine the automorphism groups of J _k and B _k for every k and prove that they are isomorphic to the dihedral group D _4k of order 4k. Research performed within the activity of INdAM–GNSAGA with the financial support of the Italian Ministry MIUR, project “Strutture Geometriche, Combinatoria e loro Applicazioni”.     

Flow-Critical Graphs

In this paper we introduce the concept of k-flow-critical graphs. These are graphs that do not admit a k-flow but such that any smaller graph obtained from it by contraction of edges or of pairs of vertices is k-flowable. Any minimal counter-example for Tutte's 3-Flow and 5-Flow Conjectures must be 3-flow-critical and 5-flow-critical, respectively. Thus, any progress towards establishing good characterizations of k-flow-critical graphs can represent progress in the study of these conjectures. We present some interesting properties satisfied by k-flow-critical graphs discovered recently.     

Families of Dot-Product Snarks on Orientable Surfaces of Low Genus

We introduce a generalized dot product and provide some embedding conditions under which the genus of a graph does not rise under a dot product with the Petersen graph. Using these conditions, we disprove a conjecture of Tinsley and Watkins on the genus of dot products of the Petersen graph and show that both Grünbaum’s Conjecture and the Berge-Fulkerson Conjecture hold for certain infinite families of snarks. Additionally, we determine the orientable genus of four known snarks and two known snark families, construct a new example of an infinite family of snarks on the torus, and construct ten new examples of infinite families of snarks on the 2-holed torus; these last constructions allow us to show that there are genus-2 snarks of every even order n ≥ 18.     

Uniquely Edge-3-Colorable Graphs and Snarks

 A cubic graph G is uniquely edge-3-colorable if G has precisely one 1-factorization. It is proved in this paper, if a uniquely edge-3-colorable, cubic graph G is cyclically 4-edge-connected, but not cyclically 5-edge-connected, then G must contain a snark as a minor. This is an approach to a conjecture that every triangle free uniquely edge-3-colorable cubic graph must have the Petersen graph as a minor. Fiorini and Wilson (1976) conjectured that every uniquely edge-3-colorable planar cubic graph must have a triangle. It is proved in this paper that every counterexample to this conjecture is cyclically 5-edge-connected and that in a minimal counterexample to the conjecture, every cyclic 5-edge-cut is trivial (an edge-cut T of G is cyclic if no component of G\T is acyclic and a cyclic edge-cut T is trivial if one component of G\T is a circuit of length |T|). Received: July 14, 1997 Revised: June 11, 1998     

Non-Bicritical Critical Snarks

 Snarks are cubic graphs with chromatic index χ^′=4. A snark G is called critical if χ^′ (G−{v,w})=3 for any two adjacent vertices v and w, and it is called bicritical if χ^′ (G−{v,w})=3 for any two vertices v and w. We construct infinite families of critical snarks which are not bicritical. This solves a problem stated by Nedela and Škoviera. Revised: January 11, 1999     

Contractible Subgraphs,Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks

We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is hamiltonian), by Thomassen (every 4-connected line graph is hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent with the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjáček and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjáček in 1997.     

Contractible subgraphs, Thomassen’s conjecture and the dominating cycle conjecture for snarks

We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian), by Thomassen (every 4-connected line graph is Hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent to the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjá?ek and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjá?ek in 1997.     

New conjectures on perfect matchings in cubic graphs

We propose three new conjectures on perfect matchings in cubic graphs. The weakest conjecture is implied by a well-known conjecture of Berge and Fulkerson. The other two conjectures are a strengthening of the first one. All conjectures are trivially verified for 3-edge-colorable cubic graphs and by computer for all snarks of order at most 34.     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.     

The total-chromatic number of some families of snarks

The total-chromatic numberχ_T(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. It is known that the problem of determining the total-chromatic number is NP-hard, and it remains NP-hard even for cubic bipartite graphs. Snarks are simple connected bridgeless cubic graphs that are not 3-edge-colourable. In this paper, we show that the total-chromatic number is 4 for three infinite families of snarks, namely, the Flower Snarks, the Goldberg Snarks, and the Twisted Goldberg Snarks. This result reinforces the conjecture that all snarks have total-chromatic number 4. Moreover, we give recursive procedures to construct a total-colouring that uses 4 colours in each case.     

Generation of Cubic Graphs and Snarks with Large Girth

We describe two new algorithms for the generation of all non‐isomorphic cubic graphs with girth at least that are very efficient for and show how these algorithms can be restricted to generate snarks with girth at least k. Our implementation of these algorithms is more than 30, respectively 40 times faster than the previously fastest generator for cubic graphs with girth at least six and seven, respectively. Using these generators we have also generated all nonisomorphic snarks with girth at least six up to 38 vertices and show that there are no snarks with girth at least seven up to 42 vertices. We present and analyze the new list of snarks with girth 6.     

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 .     

On the strong circular 5‐flow conjecture

The Strong Circular 5‐flow Conjecture of Mohar claims that each snark—with the sole exception of the Petersen graph—has circular flow number smaller than 5. We disprove this conjecture by constructing an infinite family of cyclically 4‐edge connected snarks whose circular flow number equals 5. © 2006 Wiley Periodicals, Inc. J Graph Theory