1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ @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. $\endgroup$
    – Tassle
    Jun 2, 2021 at 12:56
  • 1
    $\begingroup$ @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). $\endgroup$
    – Tassle
    Jun 3, 2021 at 7:57
  • $\begingroup$ 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 epubs.siam.org/doi/pdf/10.1137/… eprints.lse.ac.uk/43289/1/… combinatorics.org/ojs/index.php/eljc/article/view/v28i1p10 $\endgroup$
    – Lamine
    Jun 3, 2021 at 14:08
  • $\begingroup$ @Lamine Yes, I was aware of that condition :) Thanks for the documentation! $\endgroup$
    – Tassle
    Jun 7, 2021 at 16:49
  • $\begingroup$ 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. $\endgroup$
    – Juho
    Jun 17, 2021 at 11:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.