Complexity results for two kinds of colored disconnections of graphs

DOI10.1007/s10878-021-00742-0zbMath1470.05051arXiv1912.10349OpenAlexW3156876633MaRDI QIDQ2045036

Ping Li, You Chen, Xue Liang Li, Yin Di Weng

Publication date: 11 August 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.10349

zbMATH Keywords

NP-completeedge-cutvertex-cutproper disconnectionrainbow vertex-disconnection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (2)

Monochromatic vertex-disconnection colorings of graphs ⋮ The proper vertex-disconnection of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proper connection of graphs
• The rainbow vertex-disconnection in graphs
• Rainbow disconnection in graphs
• Complexity results for the proper disconnection of graphs
• Proper disconnection of graphs
• More on the rainbow disconnection in graphs
• On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}
• Rainbow connection in graphs
• Matching cutsets in graphs
• The complexity of satisfiability problems

This page was built for publication: Complexity results for two kinds of colored disconnections of graphs