On triangles in Kᵣ-minor free graphs

Original · EN

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₂,₂,₂,₂,₂ 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.