On triangles in ‐minor free graphs.

Abstract: We study graphs where each edge that is incident to a vertex of small degree (of degree at most 7 and 9, respectively) belongs to many triangles (at least 4 and 5, respectively) and show that these graphs contain a complete graph (<italic>K</italic>6 and <italic>K</italic>7, respectively) as a minor. The second case settles a problem of Nevo. Moreover, if each edge of a graph belongs to six triangles, then the graph contains a <italic>K</italic>8‐minor or contains <italic>K</italic>2, 2, 2, 2, 2 as an induced subgraph. We then show applications of these structural properties to stress freeness and coloring of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every <italic>K</italic>7‐minor free graph is 8‐colorable and every <italic>K</italic>8‐minor free graph is 10‐colorable. [ABSTRACT FROM AUTHOR]