Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9515906 | Journal of Combinatorial Theory, Series B | 2005 | 18 Pages |
Abstract
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let K8- be the graph obtained from K8 by deleting one edge. We prove a conjecture of Jakobsen that every simple graph on n⩾8 vertices and at least (11n-35)/2 edges either has a K8- minor, or is isomorphic to a graph obtained from disjoint copies of K1,2,2,2,2 and/or K7 by identifying cliques of size five.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zi-Xia Song,