Monochromatic vertex-disconnection colorings of graphs (Q2147602): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s40840-022-01284-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4226016847 / rank | |||
Normal rank |
Revision as of 02:24, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Monochromatic vertex-disconnection colorings of graphs |
scientific article |
Statements
Monochromatic vertex-disconnection colorings of graphs (English)
0 references
20 June 2022
0 references
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.
0 references
monochromatic vertex-cut
0 references
monochromatic vertex-disconnection coloring number
0 references
Nordhaus-Gaddum-type result
0 references
graph products
0 references