Folding (Q2498742)

A \(d\)-down set of a directed graph \(D\), for a fixed vertex \(x\) of \(D\) and \(d\) a positive integer, is the set of all vertices \(y\) of \(D\) such that there is a directed path of length at most \(d\) from \(y\) to \(x\). A folding of \(D\) is a coloring (or a homomorphism) of \(D\) which is injective on all the down sets of a given depth \(d\). The authors' main result finds, for any proper minor-closed class \(K\) a folding (of any prescribed depth) using a fixed number of colors. They then establish (without using the four-color theorem) the existence of a graph \(H\) of chromatic number at most five and clique number at most four such that any planar graph \(G\) is homomorphic to \(H\). This result is intermediary between the four- and five-color theorems for planar graphs and has relevance to Hadwiger's conjecture.