Monochromatic connectivity and graph products (Q2798325)

The authors consider the following problem, first introduced by \textit{Y. Caro} and \textit{R. Yuster} [Discrete Math. 311, No. 16, 1786--1792 (2011; Zbl 1223.05065)]. An MC-coloring of a graph \(G\) is a (not necessarily proper) edge coloring of G such that for every pair of vertices \(u,v \in V(G)\), there is a monochromatic \(u,v\)-path. The monochromatic connection number of \(G\), denoted \(\mathrm{mc}(G)\), is the maximum number of colors in an MC-coloring of \(G\). Caro and Yuster [loc. cit.] proved that \(\mathrm{mc}(G) \geq |E(G)| - |V(G)| + 2\) for every graph \(G\) and gave several different sufficient conditions under which equality holds.NEWLINENEWLINEThe authors prove upper and lower bounds on \(\mathrm{mc}(G \star H)\), where \(G \star H\) is the lexicographic, strong, Cartesian, or direct product of the graphs \(G\) and \(H\). They also provide sharpness examples for the lower bounds.NEWLINENEWLINEThe lower bounds are mainly based on the inequality \(\mathrm{mc}(G) \geq |E(G)| + |V(G)| + 2\), and the upper bounds are mainly based on the inequality \(\mathrm{mc}(G) \leq |E(G)| - |V(G)| + \kappa(G) + 1\), both of which are due to [loc. cit.]. The sharpness examples are based on the sufficient conditions of Caro and Yuster [loc. cit.] mentioned above.NEWLINENEWLINEIn Section 3, the authors apply their results to several specific choices of \(G\) and \(H\). There are some unsubstantiated claims in this section: in particular, the authors claim in Proposition 2 that the diameter of \(P_{L_1} \circ \cdots \circ P_{L_n}\) is at least \(3\), where \(\circ\) is the lexicographic product, but when all \(L_i \in \{1,2\}\), this product is a clique and thus has diameter \(1\). Similarly, in Proposition 3, the authors claim that the diameter of \(R_i\) is at least \(3\) for \(i \geq 3\), where \(R_i\) is the cycle on \(i\) vertices, but this is false when \(i \in \{3, 4, 5\}\).