Pentagon problem

Discussion

This question was asked by Nesetril at numerous problem sessions (and also appears as [N]). By Brook's theorem any triangle-free cubic graph is 3-colorable. Does a stronger assumption on girth of the graph imply stronger coloring properties? This problem is motivated by complexity considerations [GHN] and also by exploration of density of the homomorphism order: We write $ G \prec H $ if there is a homomorphism $ G \to H $ but there is no homomorphism $ H \to G $ . It is known that whenever $ G \prec H $ holds and $ H $ ~is not bipartite, there is a graph~ $ K $ satisfying $ G \prec K \prec H $ . A negative solution to the Pentagon problem would have the following density consequence: for each cubic graph~ $ H $ for which~ $ C_5 \prec H $ holds, there exists a cubic graph~ $ K $ satisfying $ C_5 \prec K \prec H $ (see [N]). If we replaced $ C_5 $ in the statement of the problem by a longer odd cycle, we would get a stronger statement. It is known that no such strenghthening is true. This was proved by Kostochka, Nesetril, and Smolikova [KNS] for $ C_{11} $ (hence for all $ C_l $ with $ l \ge 11 $ ), by Wanless and Wormald [WW] for $ C_9 $ , and recently by Hatami [H] for $ C_7 $ . Each of these results uses probabilistic arguments (random regular graphs), no constructive proof is known. Haggkvist and Hell [HH] proved that for every integer~ $ g $ there is a graph~ $ U_g $ with odd girth at least~ $ g $ (that is, $ U_g $ does not contain odd cycle of length less than~ $ g $ ) such that every cubic graph of odd girth at least~ $ g $ maps homomorphically to~ $ U_g $ . Here, the graph~ $ U_g $ may have large degrees. This leads to a weaker version of the Pentagon problem: Question Is it true that for every $ k $ there exists a cubic graph $ H_k $ of girth~ $ k $ and an integer~ $ g $ such that every cubic graph of girth at least~ $ g $ maps homomorphically to~ $ H_k $ ? A particular question in this direction: does a high-girth cubic graph map to the Petersen graph? As an approach to this, we mention a result of DeVos and Samal [DS]: a cubic graph of girth at least~ $ 17 $ admits a homomorphism to the Clebsch graph. In context of the Pentagon problem, the following reformulation is particularly appealing: If $ G $ ~is a cubic graph of girth at least~ $ 17 $ , then there is a cut-continuous mapping from~ $ G $ to~ $ C_5 $ ; that is, there is a mapping $ f: E(G) \to E(C_5) $ such that for any cut $ X \subseteq E(C_5) $ the preimage $ f^{-1}(X) $ is a cut. (Here by cut we mean the edge-set of a spanning bipartite subgraph. A more thorough exposition of cut-continuous mappings can be found in~[DNR].)