Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is the following conjecture true or false? (Hopefully it is true — I need it as a lemma.)

For every undirected graph $G=(V,E)$ there exist three pairwise disjoint sets of vertices $V_1,V_2,V_3$ (whose union is not necessarily $V$) such that for every $i\in\{1,2,3\}$ and for every cycle $C\in G$, $C\cap V_i\neq \emptyset$.

That is, each $V_i$ hits all cycles in $G$, and the $V_i$ are pairwise disjoint.

share|improve this question
    
The desired result in the second paragraph is untrue if $G$ is not connected (take $G$ to be the union of a cycle with some disconnected vertices). –  Vidit Nanda Jul 29 '13 at 14:40
    
If $G$ is a clique on at least 7 vertices then one of the classes must have 3 vertices and so contain a triangle disjoint from the remaining two classes. Have I understood the question correctly? –  Ben Barber Jul 29 '13 at 14:41
    
The vertex sets $V_1,V_2,V_3$ do not necessarily form a partition of $V$ (I clarified this in the question). So when $G$ is a cycle with some disconnected vertices, I just need each $V_i$ to be a vertex of the cycle. If $G$ is a clique, I would just take three different vertices. –  Ariel Jul 29 '13 at 14:46
    
Thank you for the correction. I still think cliques are a problem: if any one $V_i$ misses any 3 vertices of a clique then won't it be missing the corresponding triangle? –  Ben Barber Jul 29 '13 at 14:51
    
Oops, you're right... Thanks! –  Ariel Jul 29 '13 at 14:58

1 Answer 1

This is false for large complete graphs: eventually one of the $V_i$ will miss three vertices, and will not meet the corresponding triangle.

share|improve this answer
2  
Even any graph containing $K_4$ fails. –  Andrew D. King Jul 29 '13 at 15:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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