On colorability of graphs with forbidden minors along paths and circuits

Graphs distinguished by KrKr-minor prohibition limited to subgraphs induced by circuits have chromatic number bounded by a function f(r)f(r); precise bounds on f(r)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,3K3,3-minor free graphs is proven to be 66-colorable; K5K5 is such a graph. Consequently, a graph whose simple paths induce planar graphs is 66-colorable. We suspect the latter to be 55-colorable and we are not aware of such 55-chromatic graphs. Alternatively, (and with more accuracy) a graph whose simple paths induce {K5,K3,3−}-minor free graphs is proven to be 44-colorable (where K3,3− is the graph obtained from K3,3K3,3 by removing a single edge); K4K4 is such a graph.