EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Explicit 3‐colorings for Exponential Graphs

Adrien Argento, Pierre Charbit, Alantha Newman

Journal of Graph Theory · 07.07.2026

DOI: 10.1002/jgt.70094 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 07.07.2026. Verfasst von Adrien Argento und 2 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Argento, A., Charbit, P., & Newman, A. (2026). Explicit 3‐colorings for Exponential Graphs. Journal of Graph Theory. https://doi.org/10.1002/jgt.70094

Vancouver

Argento A, Charbit P, Newman A. Explicit 3‐colorings for Exponential Graphs. Journal of Graph Theory. 2026. doi:10.1002/jgt.70094

BibTeX
@article{Argento2026,
  author = {Argento, Adrien and Charbit, Pierre and Newman, Alantha},
  title = {Explicit 3‐colorings for Exponential Graphs},
  journal = {Journal of Graph Theory},
  year = {2026},
  doi = {10.1002/jgt.70094}
}
Kostenlos starten →