Monochromatic vertex-disconnection colorings of graphs (Q2147602): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
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
    0 references
    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
    0 references
    monochromatic vertex-cut
    0 references
    monochromatic vertex-disconnection coloring number
    0 references
    Nordhaus-Gaddum-type result
    0 references
    graph products
    0 references

    Identifiers