Hedetniemi's Conjecture Via Altermatic Number

Meysam Alishahi, Hossein HajiabolhassanarXiv 2014 · DOI · arXiv

Abstract

A 50-year-old conjecture by Hedetniemi (1966) asserts that the chromatic number of the categorical product of two graphs $G$ and $H$ is $\min\{\chi(G), \chi(H)\}$. While a general counterexample was discovered in 2019, identifying specific graph families where the conjecture holds remains a central pursuit in graph theory. In this work, we utilize the altermatic and strong altermatic numbers—two tight lower bounds for the chromatic number—to prove a relaxation of Hedetniemi's conjecture. We demonstrate that the strong altermatic number of a categorical product perfectly follows the conjectured behavior and provide a new lower bound for the chromatic number of products. These results significantly expand the known families of graphs that satisfy Hedetniemi’s conjecture.

Introduction

Hedetniemi’s Conjecture has been a cornerstone of graph coloring theory since its proposal in 1966. It concerns the chromatic number ($\chi$), the minimum number of colors required to label the vertices of a graph such that no two adjacent vertices share the same color. The conjecture focuses on the categorical product of two graphs, $G \times H$, where the vertex set is the Cartesian product $V(G) \times V(H)$, and an edge exists between $(u, v)$ and $(u', v')$ if and only if $u$ is adjacent to $u'$ in $G$ and $v$ is adjacent to $v'$ in $H$.

The conjecture states: $$\chi(G \times H) = \min\{\chi(G), \chi(H)\}$$

While it is trivial to show that $\chi(G \times H) \leq \min\{\chi(G), \chi(H)\}$, the reverse inequality has proven remarkably difficult. Although recent developments have shown the conjecture is false in the general case, the search for "tight" families—classes of graphs for which the equality holds—remains a vital area of research. This paper approaches the problem through the lens of topological graph invariants.

The Altermatic Framework

The authors introduce a methodology based on two graph invariants previously defined in their work on Kneser hypergraphs:

  1. Altermatic Number ($\zeta(G)$): A lower bound for the chromatic number derived from alternating sequences in a graph's Kneser representation.
  2. Strong Altermatic Number ($\zeta_s(G)$): A more restrictive version of the altermatic number that provides a tighter bound in specific contexts.

These invariants are "topological" in nature, meaning they relate the discrete structure of a graph to properties of associated simplicial complexes. By utilizing homomorphism properties and Kneser representations (representing graphs as intersections of sets), the authors track how these numbers behave under graph transformations and products.

Key Insights and Results

1. The Strong Altermatic Relaxation

The most significant discovery is that while the chromatic number itself is difficult to calculate for products, the strong altermatic number behaves exactly as Hedetniemi predicted for the chromatic number. The authors prove: $$\zeta_s(G \times H) = \min\{\zeta_s(G), \zeta_s(H)\}$$ This establishes $\zeta_s$ as a well-behaved proxy for the chromatic number in product operations.

2. A New Lower Bound for Products

Beyond the relaxation, the authors establish a new, tight lower bound for the chromatic number of a categorical product in terms of both altermatic and strong altermatic numbers: $$\chi(G \times H) \geq \max\{\min\{\zeta(G), \zeta_s(H) - 1\}, \min\{\zeta_s(G) - 1, \zeta(H)\}\}$$

3. Expanding Tight Families

By showing that these altermatic bounds are tight (i.e., $\zeta(G) = \chi(G)$) for specific classes, the paper identifies several families of graphs that satisfy Hedetniemi’s conjecture. These include:

  • Schrijver and Kneser graphs.
  • Kneser multigraphs.
  • Matching graphs.
  • Permutation graphs $S_r(m, n)$ for sufficiently large $m$.

Conclusion and Future Work

This research demonstrates that topological bounds like the altermatic number provide a powerful framework for tackling long-standing problems in discrete mathematics. While computing the altermatic number is known to be a computationally hard problem (NP-hard), its theoretical utility in proving the consistency of graph products is significant. Future work may involve identifying even tighter topological bounds or further classifying the structural properties that allow the altermatic number to reach the actual chromatic number, potentially uncovering even larger families of graphs that adhere to Hedetniemi's original vision.

Summary updated

Abstract

A $50$ years unsolved conjecture by Hedetniemi [{\it Homomorphisms of graphs and automata, \newblock {\em Thesis (Ph.D.)--University of Michigan}, 1966}] asserts that the chromatic number of the categorical product of two graphs $G$ and $H$ is $\min\{χ(G),χ(H)\}$. The present authors [{\it On the chromatic number of general {K}neser hypergraphs. \newblock {\em Journal of Combinatorial Theory, Series B}, 2015.}] introduced the altermatic and the strong altermatic number of graphs as two tight lower bounds for the chromatic number of graphs. In this work, we prove a relaxation of Hedetniemi's conjecture in terms of strong altermatic number. Also, we present a tight lower bound for the chromatic number of the categorical product of two graphs in term of their altermatic and strong altermatic numbers. These results enrich the family of pair graphs $\{G,H\}$ satisfying Hedetniemi's conjecture.
BibTeX
@misc{alishahi2014hedetniemi,
  author = {Meysam Alishahi and Hossein Hajiabolhassan},
  title = {{Hedetniemi's Conjecture Via Altermatic Number}},
  year = {2014},
  eprint = {1403.4404},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1403.4404},
}

Loading related content...

Figure