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:
“When the masculine mystique is pulling boys and men out into the world to growl manly noises at one another, the only power with a stronger pull on the male psyche is maternally induced guilt. The guilt is quite necessary for our moral development, but it is often uncomfortable.”
—Frank Pittman (20th century)
“Our conjectures pass upon us for truths; we will know what we do not know, and often, what we cannot know: so mortifying to our pride is the base suspicion of ignorance.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“The content of a thought depends on its external relations; on the way that the thought is related to the world, not on the way that it is related to other thoughts.”
—Jerry Alan Fodor (b. 1935)
“While the onset of puberty can vary by as much as six years, every adolescent wants to be right on the 50-yard line, right in the middle of the field. One is always too tall, too short, too thin, too fat, too hairy, too clear-skinned, too early, too late. Understandably, problems of self-image are rampant.”
—Joan Lipsitz (20th century)