On colorability of graphs with forbidden minors along paths and circuits

AbstractGraphs distinguished by Kr-minor prohibition limited to subgraphs induced by circuits have chromatic number bounded by a function f(r); precise bounds on f(r) are unknown. If minor prohibition is limited to subgraphs induced by simple paths instead of circuits, then for certain forbidden configurations, we reach tight estimates.A graph whose simple paths induce K3,3-minor free graphs is proven to be 6-colorable; K5 is such a graph. Consequently, a graph whose simple paths induce planar graphs is 6-colorable. We suspect the latter to be 5-colorable and we are not aware of such 5-chromatic graphs. Alternatively, (and with more accuracy) a graph whose simple paths induce {K5,K3,3−}-minor free graphs is proven to be 4-colorable (where K3,3− is the graph obtained from K3,3 by removing a single edge); K4 is such a graph