On triangles in K_r-minor free graphs

2013/04/19 by Albar, Boris, Gonçalves, Daniel · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1304.5468

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₆ and K₇, 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₈-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₇-minor free graph is 8-colorable and every K₈-minor free graph is 10-colorable.

Cited by

• Every graph with no K₇^\vee-minor is 6-colorable

Related

• Coloration of K₇^--minor free graphs
• Graphs with no K₉^= minor are 10-colorable
• Every graph with no K₉^-6 minor is 8-colorable
• A Note on Hadwiger's Conjecture
• Every graph with no K₈^-4 minor is 7-colorable