On colorability of graphs with forbidden minors along paths and circuits

Graphs distinguished by K r -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. h whose simple paths induce K 3 , 3 -minor free graphs is proven to be 6 -colorable; K 5 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 { K 5 , K 3 , 3 − } -minor free graphs is proven to be 4 -colorable (where K 3 , 3 − is the graph obtained from K 3 , 3 by removing a single edge); K 4 is such a graph.