Strong products of \(\chi\)-critical graphs (Q1801332): Difference between revisions

For a (finite, undirected, simple) graph \(G= (V(G),E(G))\), let \(\alpha(G)\), \(\omega(G)\), \(\chi(G)\) denote the independence number, clique number, chromatic number, respectively. The lexicographic product and the strong product of graphs \(G\) and \(H\) are denoted by \(G[H]\) and \(G\otimes H\), respectively, and the least integer \(\geq x\), \(x\in R\), by \(\lceil x\rceil\) (unfortunately, more than once also written as \([x]\) in the paper). The main result is that \[ \chi(G\otimes H)\leq \chi(G[H])\leq (\chi(G)- 1)\chi(H)+\left\lceil{\chi(H)\over \alpha(G)}\right\rceil \] holds for any graph \(H\) and any critical (with respect to vertex colouring) graph \(G\). As an interesting corollary it follows that if \(G\) has a retract which is critical and not complete, then \(\chi(G[H])<\chi(G)\chi(H)\) for every \(H\) with \(E(H)\neq\varnothing\). Furthermore, the main result is used to calculate the chromatic numbers for some strong products, namely \(\chi(\overline C_{2k+1}\otimes K_ n)= kn+\Bigl\lceil{n\over 2}\Bigr\rceil\) \((k\geq 2, n\geq 1)\), \(\chi(C_ 5\otimes C_ 5\otimes C_{2k+1})=10+\Bigl\lceil{5\over k}\Bigr\rceil\) \((k\geq 2)\), \(\chi((G+H)\otimes K_ n)=\chi(G\otimes K_ n)+\chi(H\otimes K_ n)\), \(\chi((K_{n-3}+ C_ 5)\otimes K_ m)= (n- 1)m+\Bigl\lceil{m\over 2}\Bigr\rceil\) \((n\geq 3, m\geq 1)\), where \(G+ H\), \(\overline G\), \(C_ n\) and \(K_ n\) denote the join of \(G\) and \(H\), the complement of \(G\), the cycle of length \(n\), and the complete graph on \(n\) vertices, respectively. That the upper bound for \(\chi(G\otimes H)\) in \(\chi(G\otimes H)\leq \chi(G)\chi(H)\) cannot be improved for non-critical graphs \(G\) with \(\omega(G)<\chi(G)\) is shown by the construction of two sequences of graphs \(G^ k_ n\), \(n=1,2,\dots\), for \(k= 2\) and \(k= 4\) satisfying \(| V(G^ k_ n)|= (3k+ 2)n\), \(2= \omega(G^ k_ n)< \chi(G^ k_ n)= 3\), and \(\chi(G^ k_ n\otimes K_ k)= 3k= \chi(G^ k_ n)\chi(K_ k)\).