Premium
On triangles in K r ‐minor free graphs
Author(s) -
Albar Boris,
Gonçalves Daniel
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22203
Subject(s) - combinatorics , mathematics , minor (academic) , 1 planar graph , graph minor , graph , discrete mathematics , conjecture , line graph , graph power , political science , law
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 ( K 6 and K 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 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 coloring 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.