On the chromatic number of the lexicographic product and the Cartesian sum of graphs (Q1339858)

Let \(G\) and \(H\) be graphs. Denote by \(G[H]\) their lexicographic product and by \(G\oplus H\) their Cartesian sum, defined by \(V(G \oplus H)= G\times H\) and \((a,x)\sim (b,y)\) whenever \(a\sim b\) and \(x\sim y\). Some bounds are established on the chromatic number of graphs obtained by the above products: (1) If \(G\) is non-bipartite then \(\chi(G [H]) \geq 2\chi (H)+ \lceil \chi(H)/ k\rceil\), where \(2k+1\) is the length of a shortest odd cycle of \(G\). (2) If both \(G\) and \(H\) are \(\chi\)-critical, but none of them is complete, then \(\chi (G\oplus H)\leq \chi(G) \chi(H) -1\). Using these results, the chromatic number of the lexicographic product and the Cartesian sum of any two odd cycles is computed (it is mostly equal to 7 or 8).