Explicit 3‐colorings for Exponential Graphs

ABSTRACT In 1985, El‐Zahar and Sauer showed that the chromatic number of the direct product of two 4‐chromatic graphs is 4, establishing a nontrivial case of Hedetniemi's conjecture, which has since been refuted in general. Their proof uses the concept of an exponential graph, showing that if a graph has no proper 3‐coloring, then the exponential graph has a proper 3‐coloring. This exponential graph is constructed by associating with each vertex a nonproper 3‐coloring of , and thus has a succinct representation. Some twenty years later, Tardif observed that at the crux of their proof lies the fact that a certain subgraph of the exponential graph is bipartite, and this implies that is 3‐colorable. The proof of bipartiteness of this subgraph is nonconstructive in the sense that it does not reveal to which side of a bipartition a vertex belongs. Given that this subgraph has a succinct representation, Tardif asked if there is an explicit proof of bipartiteness. In other words, in order to determine to which side of a bipartition a vertex in this subgraph belongs, can we use only the associated coloring of ? In this paper, we show that there is such an explicit bipartition. This gives an alternative proof of the aforementioned theorem of El‐Zahar and Sauer and of another theorem from the same era due to Häggkvist, Hell, Miller and Neumann Lara on the multiplicativity of odd cycles.