Counterexamples to Hedetniemi’s conjecture

Abstract

The chromatic number of $G\times H$ can be less than the minimum of the chromatic numbers of finite simple graphs $G$ and $H$.

  • [BEL] S. A. Burr, P. ErdHos, and L. Lovasz, "On graphs of Ramsey type," Ars Combinatoria, vol. 1, iss. 1, pp. 167-190, 1976.
    @ARTICLE{BEL,
      author = {Burr, S. A. and Erdős, P. and Lovasz, L.},
      title = {On graphs of {R}amsey type},
      journal = {Ars Combinatoria},
      fjournal = {Ars Combinatoria},
      volume = {1},
      year = {1976},
      number = {1},
      pages = {167--190},
      issn = {0381-7032},
      mrclass = {05C35},
      mrnumber = {0419285},
      mrreviewer = {Ralph Faudree},
      zblnumber = {0333.05120},
      }
  • [DSW] Go to document D. Duffus, B. Sands, and R. E. Woodrow, "On the chromatic number of the product of graphs," J. Graph Theory, vol. 9, iss. 4, pp. 487-495, 1985.
    @ARTICLE{DSW,
      author = {Duffus, D. and Sands, B. and Woodrow, R. E.},
      title = {On the chromatic number of the product of graphs},
      journal = {J. Graph Theory},
      fjournal = {Journal of Graph Theory},
      volume = {9},
      year = {1985},
      number = {4},
      pages = {487--495},
      issn = {0364-9024},
      mrclass = {05C15},
      mrnumber = {0890239},
      mrreviewer = {Daniel Turz\'ık},
      doi = {10.1002/jgt.3190090409},
      url = {https://doi.org/10.1002/jgt.3190090409},
      zblnumber = {0664.05019},
      }
  • [EZS] Go to document M. El-Zahar and N. W. Sauer, "The chromatic number of the product of two $4$-chromatic graphs is $4$," Combinatorica, vol. 5, iss. 2, pp. 121-126, 1985.
    @ARTICLE{EZS,
      author = {El-Zahar, M. and Sauer, N. W.},
      title = {The chromatic number of the product of two {$4$}-chromatic graphs is {$4$}},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society},
      volume = {5},
      year = {1985},
      number = {2},
      pages = {121--126},
      issn = {0209-9683},
      mrclass = {05C15},
      mrnumber = {0815577},
      mrreviewer = {Ortrud R. Oellermann},
      doi = {10.1007/BF02579374},
      url = {https://doi.org/10.1007/BF02579374},
      zblnumber = {0575.05028},
      }
  • [Erd] Go to document P. ErdHos, "Graph theory and probability," Canadian J. Math., vol. 11, pp. 34-38, 1959.
    @ARTICLE{Erd,
      author = {Erdős, P.},
      title = {Graph theory and probability},
      journal = {Canadian J. Math.},
      fjournal = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
      volume = {11},
      year = {1959},
      pages = {34--38},
      issn = {0008-414X},
      mrclass = {55.00},
      mrnumber = {0102081},
      mrreviewer = {W. Moser},
      doi = {10.4153/CJM-1959-003-9},
      url = {https://doi.org/10.4153/CJM-1959-003-9},
      zblnumber = {0084.39602},
      }
  • [HHMNL] Go to document R. Häggkvist, P. Hell, D. J. Miller, and V. Neumann Lara, "On multiplicative graphs and the product conjecture," Combinatorica, vol. 8, iss. 1, pp. 63-74, 1988.
    @ARTICLE{HHMNL,
      author = {Häggkvist, R. and Hell, P. and Miller, D. J. and Neumann Lara, V.},
      title = {On multiplicative graphs and the product conjecture},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society},
      volume = {8},
      year = {1988},
      number = {1},
      pages = {63--74},
      issn = {0209-9683},
      mrclass = {05C38 (05C75)},
      mrnumber = {0951994},
      doi = {10.1007/BF02122553},
      url = {https://doi.org/10.1007/BF02122553},
      zblnumber = {0657.05028},
      }
  • [HM] Go to document H. Hajiabolhassan and F. Meunier, "Hedetniemi’s conjecture for Kneser hypergraphs," J. Combin. Theory Ser. A, vol. 143, pp. 42-55, 2016.
    @ARTICLE{HM,
      author = {Hajiabolhassan, Hossein and Meunier, Frédéric},
      title = {Hedetniemi's conjecture for {K}neser hypergraphs},
      journal = {J. Combin. Theory Ser. A},
      fjournal = {Journal of Combinatorial Theory. Series A},
      volume = {143},
      year = {2016},
      pages = {42--55},
      issn = {0097-3165},
      mrclass = {05C15 (05C65 05C76)},
      mrnumber = {3519814},
      mrreviewer = {Xiaofeng Gu},
      doi = {10.1016/j.jcta.2016.05.002},
      url = {https://doi.org/10.1016/j.jcta.2016.05.002},
      zblnumber = {1342.05094},
      }
  • [Haj] Go to document A. Hajnal, "The chromatic number of the product of two $\aleph_1$-chromatic graphs can be countable," Combinatorica, vol. 5, iss. 2, pp. 137-139, 1985.
    @ARTICLE{Haj,
      author = {Hajnal, A.},
      title = {The chromatic number of the product of two {$\aleph_1$}-chromatic graphs can be countable},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society},
      volume = {5},
      year = {1985},
      number = {2},
      pages = {137--139},
      issn = {0209-9683},
      mrclass = {05C15 (04A20)},
      mrnumber = {0815579},
      mrreviewer = {Andrzej Pelc},
      doi = {10.1007/BF02579376},
      url = {https://doi.org/10.1007/BF02579376},
      zblnumber = {0575.05029},
      }
  • [Hedetniemi] Go to document S. T. Hedetniemi, Homomorphisms of Graphs and Automata, ProQuest LLC, Ann Arbor, MI, 1966.
    @BOOK{Hedetniemi,
      author = {Hedetniemi, Stephen Travis},
      title = {Homomorphisms of Graphs and Automata},
      note = {Thesis (Ph.D.)--University of Michigan},
      publisher = {ProQuest LLC, Ann Arbor, MI},
      year = {1966},
      pages = {92},
      mrclass = {Thesis},
      mrnumber = {2615860},
      url = {http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:6701754},
      zblnumber = {},
      }
  • [Klavzar] Go to document S. Klavvzar, "Coloring graph products—a survey," Discrete Math., vol. 155, iss. 1-3, pp. 135-145, 1996.
    @ARTICLE{Klavzar,
      author = {Klavžar, Sandi},
      title = {Coloring graph products---a survey},
      note = {Combinatorics (Acireale, 1992)},
      journal = {Discrete Math.},
      fjournal = {Discrete Mathematics},
      volume = {155},
      year = {1996},
      number = {1-3},
      pages = {135--145},
      issn = {0012-365X},
      mrclass = {05C15 (05C90)},
      mrnumber = {1401366},
      mrreviewer = {B. Manvel},
      doi = {10.1016/0012-365X(94)00377-U},
      url = {https://doi.org/10.1016/0012-365X(94)00377-U},
      zblnumber = {0857.05035},
      }
  • [PR] Go to document S. Poljak and V. Rödl, "On the arc-chromatic number of a digraph," J. Combin. Theory Ser. B, vol. 31, iss. 2, pp. 190-198, 1981.
    @ARTICLE{PR,
      author = {Poljak, S. and Rödl, V.},
      title = {On the arc-chromatic number of a digraph},
      journal = {J. Combin. Theory Ser. B},
      fjournal = {Journal of Combinatorial Theory. Series B},
      volume = {31},
      year = {1981},
      number = {2},
      pages = {190--198},
      issn = {0095-8956},
      mrclass = {05C15 (05C20)},
      mrnumber = {0630982},
      mrreviewer = {R. C. Entringer},
      doi = {10.1016/S0095-8956(81)80024-X},
      url = {https://doi.org/10.1016/S0095-8956(81)80024-X},
      zblnumber = {0472.05024},
      }
  • [Sau] Go to document N. Sauer, "Hedetniemi’s conjecture—a survey," Discrete Math., vol. 229, iss. 1-3, pp. 261-292, 2001.
    @ARTICLE{Sau,
      author = {Sauer, Norbert},
      title = {Hedetniemi's conjecture---a survey},
      note = {Combinatorics, graph theory, algorithms and applications},
      journal = {Discrete Math.},
      fjournal = {Discrete Mathematics},
      volume = {229},
      year = {2001},
      number = {1-3},
      pages = {261--292},
      issn = {0012-365X},
      mrclass = {05C15},
      mrnumber = {1815610},
      mrreviewer = {Richard C. Brewster},
      doi = {10.1016/S0012-365X(00)00213-2},
      url = {https://doi.org/10.1016/S0012-365X(00)00213-2},
      zblnumber = {0971.05050},
      }
  • [Tard2] Go to document C. Tardif, "Multiplicative graphs and semi-lattice endomorphisms in the category of graphs," J. Combin. Theory Ser. B, vol. 95, iss. 2, pp. 338-345, 2005.
    @ARTICLE{Tard2,
      author = {Tardif, Claude},
      title = {Multiplicative graphs and semi-lattice endomorphisms in the category of graphs},
      journal = {J. Combin. Theory Ser. B},
      fjournal = {Journal of Combinatorial Theory. Series B},
      volume = {95},
      year = {2005},
      number = {2},
      pages = {338--345},
      issn = {0095-8956},
      mrclass = {05C15},
      mrnumber = {2171371},
      mrreviewer = {A. Pultr},
      doi = {10.1016/j.jctb.2005.06.002},
      url = {https://doi.org/10.1016/j.jctb.2005.06.002},
      zblnumber = {1078.05081},
      }
  • [Tard] C. Tardif, "Hedetniemi’s conjecture, 40 years later," Graph Theory Notes N. Y., vol. 54, pp. 46-57, 2008.
    @ARTICLE{Tard,
      author = {Tardif, Claude},
      title = {Hedetniemi's conjecture, 40 years later},
      journal = {Graph Theory Notes N. Y.},
      fjournal = {Graph Theory Notes of New York},
      volume = {54},
      year = {2008},
      pages = {46--57},
      issn = {1040-8118},
      mrclass = {05C15},
      mrnumber = {2445666},
      zblnumber = {},
      }
  • [Rin] Go to document A. Rinot, "Hedetniemi’s conjecture for uncountable graphs," J. Eur. Math. Soc. (JEMS), vol. 19, iss. 1, pp. 285-298, 2017.
    @ARTICLE{Rin,
      author = {Rinot, Assaf},
      title = {Hedetniemi's conjecture for uncountable graphs},
      journal = {J. Eur. Math. Soc. (JEMS)},
      fjournal = {Journal of the European Mathematical Society (JEMS)},
      volume = {19},
      year = {2017},
      number = {1},
      pages = {285--298},
      issn = {1435-9855},
      mrclass = {03E75 (03E35 05C15 05C76)},
      mrnumber = {3584564},
      mrreviewer = {A. Kanamori},
      doi = {10.4171/JEMS/666},
      url = {https://doi.org/10.4171/JEMS/666},
      zblnumber = {06682211},
      }
  • [VPV] Go to document M. Valencia-Pabon and J. Vera, "Independence and coloring properties of direct products of some vertex-transitive graphs," Discrete Math., vol. 306, iss. 18, pp. 2275-2281, 2006.
    @ARTICLE{VPV,
      author = {Valencia-Pabon, Mario and Vera, Juan},
      title = {Independence and coloring properties of direct products of some vertex-transitive graphs},
      journal = {Discrete Math.},
      fjournal = {Discrete Mathematics},
      volume = {306},
      year = {2006},
      number = {18},
      pages = {2275--2281},
      issn = {0012-365X},
      mrclass = {05C15 (05C69)},
      mrnumber = {2255625},
      doi = {10.1016/j.disc.2006.04.013},
      url = {https://doi.org/10.1016/j.disc.2006.04.013},
      zblnumber = {1111.05040},
      }
  • [Wel] Go to document E. Welzl, "Symmetric graphs and interpretations," J. Combin. Theory Ser. B, vol. 37, iss. 3, pp. 235-244, 1984.
    @ARTICLE{Wel,
      author = {Welzl, Emo},
      title = {Symmetric graphs and interpretations},
      journal = {J. Combin. Theory Ser. B},
      fjournal = {Journal of Combinatorial Theory. Series B},
      volume = {37},
      year = {1984},
      number = {3},
      pages = {235--244},
      issn = {0095-8956},
      mrclass = {05C15 (05C25)},
      mrnumber = {0769366},
      mrreviewer = {Pavol Hell},
      doi = {10.1016/0095-8956(84)90056-X},
      url = {https://doi.org/10.1016/0095-8956(84)90056-X},
      zblnumber = {0547.05058},
      }
  • [Wrochna] Go to document M. Wrochna, "On inverse powers of graphs and topological implications of Hedetniemi’s conjecture," J. Combin. Theory B, 2019.
    @ARTICLE{Wrochna,
      author = {Wrochna, M.},
      title = {On inverse powers of graphs and topological implications of {H}edetniemi's conjecture},
      journal = {J. Combin. Theory B},
      year = {2019},
      note = {Available online 27 March 2019},
      doi = {10.1016/j.jctb.2019.02.008},
      zblnumber = {},
      }
  • [Zhu] Go to document X. Zhu, "A survey on Hedetniemi’s conjecture," Taiwanese J. Math., vol. 2, iss. 1, pp. 1-24, 1998.
    @ARTICLE{Zhu,
      author = {Zhu, Xuding},
      title = {A survey on {H}edetniemi's conjecture},
      journal = {Taiwanese J. Math.},
      fjournal = {Taiwanese Journal of Mathematics},
      volume = {2},
      year = {1998},
      number = {1},
      pages = {1--24},
      issn = {1027-5487},
      mrclass = {05C15 (05-02)},
      mrnumber = {1609464},
      mrreviewer = {Gary MacGillivray},
      doi = {10.11650/twjm/1500406890},
      url = {https://doi.org/10.11650/twjm/1500406890},
      zblnumber = {0906.05024},
      }
  • [Zhu2] Go to document X. Zhu, "The fractional version of Hedetniemi’s conjecture is true," European J. Combin., vol. 32, iss. 7, pp. 1168-1175, 2011.
    @ARTICLE{Zhu2,
      author = {Zhu, Xuding},
      title = {The fractional version of {H}edetniemi's conjecture is true},
      journal = {European J. Combin.},
      fjournal = {European Journal of Combinatorics},
      volume = {32},
      year = {2011},
      number = {7},
      pages = {1168--1175},
      issn = {0195-6698},
      mrclass = {05C72 (05C15 05C55)},
      mrnumber = {2825542},
      mrreviewer = {Peter D. Johnson, Jr.},
      doi = {10.1016/j.ejc.2011.03.004},
      url = {https://doi.org/10.1016/j.ejc.2011.03.004},
      zblnumber = {1229.05108},
      }

Authors

Yaroslav Shitov