Monochromatic vertex-disconnection colorings of graphs (Q2147602)

Let \(G\) be a vertex-coloured connected graph (adjacent vertices can be given the same colour). A subset \(U\) of the vertex-set of \(G\) is said to be monochromatic if all the vertices of \(U\) are assigned the same colour. The graph \(G\) is said to be monochromatic vertex-disconnected if, for a two distinct vertices \(x\) and \(y\), there is a monochromatic subset \(S\) of the vertex-set of \(G\) such that, if \(x\) and \(y\) are not adjacent, then they are in different components of \(G-S\), and if \(x\) and \(y\) are adjacents, then at least one of \(x\) or \(y\) has the same colour as \(S\) and they belong to different components of \((G-S)-xy\), where \(xy\) denotes the edge \(\{x,y\}\). The monochromatic vertex-disconnection number of \(G\), denoted by mvd\((G)\), is the maximum number of colours possible which makes \(G\) monochromatic vertex-disconnected. This parameter is analogous to the rainbow vertex-disconnection number introduced in [\textit{X. Q. Bai} et al., Acta Math. Sin., Engl. Ser. 37, No. 2, 249--261 (2021; Zbl 1462.05130)]. In this paper, the authors present sufficient conditions for \(G\) to have mvd\((G)=1\), and they also show that, in the model \(G(n,\frac{1}{2})\), almost every graph \(G\) does have mvd\((G)=1\). They prove some Nordhau-Gaddum-type results and they also investigate the monochromatic vertex-disconnection number for the Cartesian product, the strong product, the lexicographic product, and the direct product.