Date of Graduation
Eberly College of Arts and Sciences
In this paper, we present three results: (1) Let G be a (k + 2)-connected non-(k - 3)-apex graph where k ≥ 2. If G contains three k-cliques, say L 1, L2, L3, such that |Li ∩ Lj| ≤ k - 2 (1 ≤ i < j ≤ 3), then G contains a Kk +2 as a minor. (2) Let G be a 6-connected claw-free graph. If delta(G) ≥ 7 and G contains three disjoint 5-cliques, say Ll, L2, L3, then G contains a K7 as a minor. (3) There is a function h : N → N, such that, for every 4-connected graph G with minimum degree at least five embedded in a surface with Euler genus g and face-width at least h(g), every longest circuit of the graph G has a chord.
Niu, Jianbing, "Graph minor" (2004). Graduate Theses, Dissertations, and Problem Reports. 2122.