Complexity results for two kinds of colored disconnections of graphs

You Chen (), Ping Li (), Xueliang Li () and Yindi Weng ()
Additional contact information
You Chen: Nankai University
Ping Li: Nankai University
Xueliang Li: Nankai University
Yindi Weng: Nankai University

Journal of Combinatorial Optimization, 2021, vol. 42, issue 1, No 3, 40-55

Abstract: Abstract The concept of rainbow disconnection number of graphs was introduced by Chartrand et al. (2018). Inspired by this concept, we put forward the concepts of rainbow vertex-disconnection and proper disconnection in graphs. In this paper, we first show that it is NP-complete to decide whether a given edge-colored graph G has a proper edge-cut separating two specified vertices, even though the graph G has $$\Delta (G)=4$$ Δ ( G ) = 4 or is bipartite. Then, for a graph G with $$\Delta (G)\le 3$$ Δ ( G ) ≤ 3 we show that $$pd(G)\le 2$$ p d ( G ) ≤ 2 and distinguish the graphs with $$pd(G)=1$$ p d ( G ) = 1 and 2, respectively. We also show that it is NP-complete to decide whether a given vertex-colored graph G is rainbow vertex-disconnected, even though the graph G has $$\Delta (G)=3$$ Δ ( G ) = 3 or is bipartite.

Keywords: Edge-cut; Vertex-cut; Rainbow (vertex-)disconnection; Proper disconnection; NP-complete; 05C15; 05C40; 68Q25; 68Q17; 68R10 (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00742-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:42:y:2021:i:1:d:10.1007_s10878-021-00742-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00742-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().