On triangles in K_r-minor free graphs

Abstract

We study graphs where each edge adjacent to a vertex of small degree (7 and 9, respectively) belongs to many triangles (4 and 5, respectively) and show that these graphs contain a complete graph (K_6 and K_7, respectively) as a minor. The second case settles a problem of Nevo (Nevo, 2007). Morevover if each edge of a graph belongs to 6 triangles then the graph contains a K_8-minor or contains K_{2,2,2,2,2} as an induced subgraph. We then show applications of these structural properties to stress freeness and coloration of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K_7-minor free graph is 8-colorable and every K_8-minor free graph is 10-colorable.

28 pages

References in corpus (1)

• Thomassen's Choosability Argument Revisited

Cited by in corpus (9)

• Defective colouring of graphs excluding a subgraph or minor
• The extremal function for Petersen minors
• A Note on Hadwiger's Conjecture
• Hadwiger's conjecture for graphs with forbidden holes
• Coloring Graphs with Forbidden Minors
• Clique Minors in Double-critical Graphs
• Double-critical graph conjecture for claw-free graphs
• Detecting minors in matroids through triangles
• Coloration of $K_7^{-}$-minor free graphs