Given an undirected graph, possibly with multiple edges connecting the same pair of points. Some edges are white, others black. What is the largest constant $c$ such that we can always color the vertices black and white so that for each color, at least a fraction $c$ of the edges of that color is adjacent to at least one vertex of that color?

It is not hard to see that $c\leq 2/3$: If we have three vertices such that each pair is connected by a black edge and a white edge, then one of the colors will have only $2$ out of $3$ vertices adjacent to an edge of that color. Also Shayan shows below that $c\geq 1/2$. What is the best $c$ between $1/2$ and $2/3$?

  • 1
    $\begingroup$ @Apple a fraction c of the edges of $\color{red}{\text{that}}$ color is ... thanks for the clarification ... I see now (thanks again) $\ddot \smile$ $\endgroup$ Jul 13 '18 at 18:25

I have the answer for c = 1/2.

Just consider the white edges. As you might know, for every (undirected) graph you can can delete at most half of edges to get a bipartite graph. We'll call the partitions A and B. So there are at least half of the white edges between the group A and B. So if we color all the vertices of which ever group to white, there are at least half of the white edges which is connected to at least one white vertex. So we can choose to paint all the vertices of A to white, or all the vertices of B to white. (We'll choose it later)

Now that we partitioned the vertices into two groups, we want to see which partition should we paint to black, the other partition would be colored to white, and as mentioned, for whites the conditions is held.

The black edges between two partitions, will be connected to at least one black vertex whichever way. Now see the black edges inside the partitions. If black edges in partition A is more, we'll color all the vertices of the A to black. And if black edges in partition B is more, we'll do otherwise.

You can see for white and black the conditions is held.

Proof for the theorem used in this solution: Given a graph, partition it into 2 groups whichever way. If there was a vertex in one group, which more than half of its neighbors are in its group, move the vertex to the other partition. You can see this operation will end, and when ended, for each vertex at least half of its neighbors is in the other group. So at least half of the edges is in-between the partitions.

Update: In this proof, by neighbors we mean the number of edges connected to one vertex.

  • $\begingroup$ Let A, B , C, and D be vertices. There is a white edge between A and B, a white edge between C an D, a black edge between B and C, and 3 white edges between B an C. {A, D} and {B, C} is a valid partition of the white edges graph. {A, D} is white and {B, C} is black. But only 2/5 of the white edges are adjacent to white vertices. {A, C} and {B, D} is a partition that works, but your algorithm as it stands won't always find it. $\endgroup$
    – Steve B
    Jul 4 '18 at 6:43
  • $\begingroup$ @SteveB {A, D} and {B, C} is not a valid partition for white edges. There are 2 white edges in-between the partitions, since there are 5 white edges at total. $\endgroup$
    – Shayan
    Jul 4 '18 at 7:28
  • $\begingroup$ I followed the algorithm in the proof in the last paragraph. I partitioned the graph into 2 groups. No vertex had more than half its neighbors in its group, so no changes had to be made. That left me with the partition {A, D}, {B, C}. However, I found another algorithm which will always produce the partition {A, C}, {B, D}, so I withdraw any quibbles about your answer. $\endgroup$
    – Steve B
    Jul 4 '18 at 8:15
  • $\begingroup$ @SteveB You're right. In the proof i forgot to mention by neighbors, i meant the number of edges connected to it. I'll correct it. So now, when the partitions are {A, D} and {B, C}, algorithm doesn't end, because vertex B has 3 neighbors (although, all of them are vertex C), in its group, while having 4 neighbors at total. $\endgroup$
    – Shayan
    Jul 5 '18 at 3:42
  • $\begingroup$ Just as a note, you can also get $c=\frac{1}{2}$ by probabilistic means. Namely, first WLOG thicken the white and black edges so that there are the same amount of each total. Then uniformly randomly color the vertices; in expectation 3/4 of all edges will be next to a vertex of their color, hence at least 1/2 of each color will have this property. $\endgroup$
    – Apple
    Jul 13 '18 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.