In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.
It is an unsolved problem, posed by George Szekeres and Paul Seymour and known as the cycle double cover conjecture, whether every bridgeless graph has a cycle double cover. The conjecture can equivalently be formulated in terms of graph embeddings, and in that context is also known as the circular embedding conjecture.
The usual formulation of the cycle double cover conjecture asks whether every bridgeless undirected graph has a collection of cycles such that each edge of the graph is contained in exactly two of the cycles. The requirement that the graph be bridgeless is an obvious necessary condition for such a set of cycles to exist, because a bridge cannot belong to any cycle. A collection of cycles satisfying the condition of the cycle double cover conjecture is called a cycle double cover. Some graphs such as cycle graphs and bridgeless cactus graphs can only be covered by using the same cycle more than once, so this sort of duplication is allowed in a cycle double cover.
snark (graph theory)
A snark is a special case of a bridgeless graph, having the additional properties that every vertex has exactly three incident edges (that is, the graph is cubic) and that it is not possible to partition the edges of the graph into three perfect matchings (that is, the graph has no 3-edge coloring, and by Vizing's theorem has chromatic index 4). It turns out that snarks form the only difficult case of the cycle double cover conjecture: if the conjecture is true for snarks, it is true for any graph.
observes that, in any potential minimal counterexample to the cycle double cover conjecture, all vertices must have three or more incident edges.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree Δ of the graph. At least Δ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which Δ colors suffice, and "class two" graphs for which Δ + 1 colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most Δ+μ colors, where μ is the multiplicity of the multigraph.
In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist. One of the equivalent forms of the four color theorem is that every snark is a non-planar graph. Research on snarks originated in Peter G.
In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors.
Given a graph H and a set of graphs F, let ex(n, H, F) denote the maximum possible number of copies of H in an T-free graph on n vertices. We investigate the function ex(n, H, F), when H and members of F are cycles. Let C-k denote the cycle of length k and ...
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...