Tensor product G×H: (u₁,v₁)~(u₂,v₂) iff u₁u₂∈E(G) AND v₁v₂∈E(H). Both coordinates must move along edges simultaneously. |E(G×H)|=2|E₁|·|E₂|. Hedetniemi's conjecture (1966): χ(G×H) = min(χ(G),χ(H)).
How to Use
Select G and H:
- |V|: |V₁|·|V₂|
- |E|: 2|E₁|·|E₂|
- χ: Hedetniemi bound
Hedetniemi's Conjecture
Conjectured (1966): χ(G×H) = min(χ(G),χ(H)). Proved for many cases. Shitov (2019) found a counterexample! But only for very large chromatic numbers. The conjecture holds for small χ and special graph families.
Properties
Commutative, associative. G×H may be disconnected even if G,H connected (iff both are bipartite or both non-bipartite). The adjacency matrix A(G×H) = A(G)⊗A(H) (Kronecker product).
Step-by-Step Instructions
- 1Select G, H.
- 2Compute G×H.
- 3Count vertices/edges.
- 4Check connectivity.
- 5Compare to Cartesian.