Stronger Conjectures and Related Problems
A stronger version of the circular embedding conjecture that has also been considered is the conjecture that every biconnected graph has a circular embedding on an orientable manifold. In terms of the cycle double cover conjecture, this is equivalent to the conjecture that there exists a cycle double cover, and an orientation for each of the cycles in the cover, such that for every edge e the two cycles that cover e are oriented in opposite directions through e.
Alternatively, strengthenings of the conjecture that involve colorings of the cycles in the cover have also been considered. The strongest of these is a conjecture that every bridgeless graph has a circular embedding on an orientable manifold in which the faces can be 5-colored. If true, this would imply a conjecture of W. T. Tutte that every bridgeless graph has a nowhere-zero 5-flow.
A stronger type of embedding than a circular embedding is a polyhedral embedding, an embedding of a graph on a surface in such a way that every face is a simple cycle and every two faces that intersect do so in either a single vertex or a single edge. (In the case of a cubic graph, this can be simplified to a requirement that every two faces that intersect do so in a single edge.) Thus, in view of the reduction of the cycle double cover conjecture to snarks, it is of interest to investigate polyhedral embeddings of snarks. Unable to find such embeddings, Branko Grünbaum conjectured that they do not exist, but Kochol (2009a, 2009b) disproved Grünbaum's conjecture by finding a snark with a polyhedral embedding.
Read more about this topic: Cycle Double Cover
Famous quotes containing the words stronger, conjectures, related and/or problems:
“He made all these and more,
Made all we see; and us, in spite: how else?
He could not, Himself, make a second self
To be His mate: as well have made Himself:
He would not make what He mislikes or slights,
An eyesore to Him, or not worth His pains;
But did, in envy, listlessness, or sport,
Make what Himself would fain, in a manner, be—
Weaker in most points, stronger in a few,
Worthy, and yet mere playthings all the while,
Things He admires and mocks too,—”
—Robert Browning (1812–1889)
“After all, it is putting a very high price on one’s conjectures to have a man roasted alive because of them.”
—Michel de Montaigne (1533–1592)
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“There is an enormous chasm between the relatively rich and powerful people who make decisions in government, business, and finance and our poorer neighbors who must depend on these decisions to alleviate the problems caused by their lack of power and influence.”
—Jimmy Carter (James Earl Carter, Jr.)