排序方式: 共有5条查询结果,搜索用时 15 毫秒
1
1.
Eckhard Steffen 《Discrete Mathematics》2004,280(1-3):191-214
Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let ck be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r3=|E|−c3 and
. We show that on one side r3 and r2 bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r3 and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr3. For k=2,3, let ζk denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other. 相似文献
2.
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. 相似文献
3.
Eckhard Steffen 《Discrete Mathematics》2010,310(3):385-389
In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let ω(G) be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph G. Tutte’s conjecture is equivalent to its restriction to cubic graphs with ω≥2. We show that if a cubic graph G has no edge cut with fewer than edges that separates two odd cycles of a minimum 2-factor of G, then G has a nowhere-zero 5-flow. This implies that if a cubic graph G is cyclically n-edge connected and , then G has a nowhere-zero 5-flow. 相似文献
4.
On embeddings of snarks in the torus 总被引:1,自引:0,他引:1
Andrej Vodopivec 《Discrete Mathematics》2008,308(10):1847-1849
A condition on cubic graphs G1 and G2 is presented, which implies that a dot product G1·G2 exists, which has an embedding in the torus. Using this condition we prove that for every positive integer n a dot product of n copies of the Petersen graph exists, which can be embedded in the torus. This disproves a conjecture of Watkins and Tinsley and answers a question by Mohar. 相似文献
5.
Gunnar Brinkmann Jan Goedgebeur Jonas Hägglund Klas Markström 《Journal of Combinatorial Theory, Series B》2013
For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for snarks, the class of non-trivial 3-regular graphs which cannot be 3-edge coloured. 相似文献
1