<p>Consider a simple graph <span class="math-container">$G$</span> where each edge is either red or blue. I'm interested in the following notion of connectivity:</p>
<p>Two vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span> are said to be connected if there is a path connecting them consisting only of red edges and another consisting only of blue edges.</p>
<p>I'm particularly interested in what I think of as &quot;totally disconnected graphs&quot;, that is 2-edge-colored graphs such that every induced subgraph is disconnected (meaning that there are two vertices which are not connected according to the above definition of connectivity).</p>
<p>Have these notions been considered in the literature?</p>

CC BY-SA 4.0
2021-06-02T12:56:05.097Z
@InuyashaYagami The problem with this reduction is that it doesn't preserve the "totally disconnected" property, which is what I am primarily interested in. More specifically, I want to know which graphs have a large totally disconnected induced subgraph (in other words, what are the weakest conditions on G for which we can derive strong lower bounds on the size of the largest totally disconnected induced subgraph of G). I'm doubtful this exact question has been studied, but I would be very happy to be proven otherwise.
Tassle
CC BY-SA 4.0
2021-06-03T07:57:28.573Z
@InuyashaYagami I think you misundertood the definition of "totally disconnected" where for every induced subgraph I consider connectivity inside that subgraph. The simplest counter-example to your claim is a triangle with two red edges and one blue edge. Your reduction produce a graph with exactly one edge (the blue one). But the graph is totally disconnected, as the induced subgraph consisting of the two vertices incident to the blue edge is disconnected (there is no red path).
Tassle
CC BY-SA 4.0
2021-06-03T14:08:05.243Z
Trivial observation (I guess that you are aware of): a sufficient condition for a graph to be "totally disconnected" is that for each induced subgraph of size $k$, there are less than $k-1$ red (resp. blue) edges. The closest works I found are the following  https://epubs.siam.org/doi/pdf/10.1137/110856332?casa_token=OAL66nDPn_sAAAAA:Y1LZmYKmKprkXxqPFj8EZhQvVlad5Z_Dw_s8Tp9NsMth5WK6ghhgYGE9ssAsYK1T4QyTboCCcpo http://eprints.lse.ac.uk/43289/1/Skokan_Monochromatic_cycles_2-coloured_2012.pdf https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i1p10
Lamine
CC BY-SA 4.0
2021-06-07T16:49:24.013Z
@Lamine Yes, I was aware of that condition :) Thanks for the documentation!
Tassle
CC BY-SA 4.0
2021-06-17T11:16:01.957Z
What's the motivation for this problem, if I may ask? I don't know whether this has been studied before, but there are similar recent notions stemming from e.g., rainbow connectivity including rainbow disconnection, proper disconnection & monochromatic disconnection. There's also a recent book from Chartrand et al. on color connection and disconnection that might contains further clues.
Juho
<graph-theory><graph-colouring>
Has this notion of connectivity in edge-colored graphs been studied?
Tassle
# Has this notion of connectivity in edge-colored graphs been studied?

(Asked by: username_0 on 2021-06-01)

Consider a simple graph $G$ where each edge is either red or blue. I'm interested in the following notion of connectivity:

Two vertices $u$ and $v$ are said to be connected if there is a path connecting them consisting only of red edges and another consisting only of blue edges.

I'm particularly interested in what I think of as "totally disconnected graphs", that is 2-edge-colored graphs such that every induced subgraph is disconnected (meaning that there are two vertices which are not connected according to the above definition of connectivity).

Have these notions been considered in the literature?

**Tags:** graph-theory, graph-colouring
> **Comments:**
> **username_0**: @InuyashaYagami The problem with this reduction is that it doesn't preserve the "totally disconnected" property, which is what I am primarily interested in. More specifically, I want to know which graphs have a large totally disconnected induced subgraph (in other words, what are the weakest conditions on G for which we can derive strong lower bounds on the size of the largest totally disconnected induced subgraph of G). I'm doubtful this exact question has been studied, but I would be very happy to be proven otherwise.  
> **username_0**: @InuyashaYagami I think you misundertood the definition of "totally disconnected" where for every induced subgraph I consider connectivity inside that subgraph. The simplest counter-example to your claim is a triangle with two red edges and one blue edge. Your reduction produce a graph with exactly one edge (the blue one). But the graph is totally disconnected, as the induced subgraph consisting of the two vertices incident to the blue edge is disconnected (there is no red path).  
> **username_1**: Trivial observation (I guess that you are aware of): a sufficient condition for a graph to be "totally disconnected" is that for each induced subgraph of size $k$, there are less than $k-1$ red (resp. blue) edges. The closest works I found are the following  https://epubs.siam.org/doi/pdf/10.1137/110856332?casa_token=OAL66nDPn_sAAAAA:Y1LZmYKmKprkXxqPFj8EZhQvVlad5Z_Dw_s8Tp9NsMth5WK6ghhgYGE9ssAsYK1T4QyTboCCcpo http://eprints.lse.ac.uk/43289/1/Skokan_Monochromatic_cycles_2-coloured_2012.pdf https://www.combinatorics.org/ojs/index.php/eljc/article/view/v28i1p10  
> **username_0**: @Lamine Yes, I was aware of that condition :) Thanks for the documentation!  
> **username_2**: What's the motivation for this problem, if I may ask? I don't know whether this has been studied before, but there are similar recent notions stemming from e.g., rainbow connectivity including rainbow disconnection, proper disconnection & monochromatic disconnection. There's also a recent book from Chartrand et al. on color connection and disconnection that might contains further clues.  

---

## 0 answers

