Vizing’s conjecture for chordal graphs

Vizing conjectured that γ ( G □ H ) ≥ γ ( G ) γ ( H ) for every pair G , H of graphs, where “ □ ” is the Cartesian product, and γ ( G ) is the domination number of the graph G . Denote by γ i ( G ) the maximum, over all independent sets I in G , of the minimal number of vertices needed to dominate I . We prove that γ ( G □ H ) ≥ γ i ( G ) γ ( H ) . Since for chordal graphs γ i = γ , this proves Vizing’s conjecture when G is chordal.