A new bound for Vizing's conjecture

Abstract

For any graph $G$, we define the power $\ddot{I}€(G)$ as the minimum of the largest number of neighbors in a ${\hat{I}}^3$-set of $G$, of any vertex, taken over all ${\hat{I}}^3$-sets of $G$. We show that ${\hat{I}}^3(G\square H)\ge \frac{\ddot{I}€(G)}{2\ddot{I}€(G)-1}{\hat{I}}^3(G){\hat{I}}^3(H)$. Our methods allow us to prove the following statements for any graphs $G$ and $H$, (1) ${\hat{I}}^3(G\square H)\ge \frac{\lceil \frac{{\hat{I}}^3(G)}{2}\rceil }{2\lceil \frac{{\hat{I}}^3(G)}{2}\rceil -1}{\hat{I}}^3(G){\hat{I}}^3(H)$ for odd ${\hat{I}}^3(G)$, (2) ${\hat{I}}^3(G\square H)\ge \frac{{\hat{I}}^3(G)}{2{\hat{I}}^3(G)-2}{\hat{I}}^3(G){\hat{I}}^3(H)$, for even ${\hat{I}}^3(G)$, and (3) a short proof of Vizing's conjecture where ${\hat{I}}^3(G)=3$. Our argument relies on establishing efficient correspondences between dominating vertices and subsets of their neighborhoods and then showing a sufficient number of dominating vertices that horizontally dominate vertically undominated cells.

14 pages