Let $V$ be the vertices of the cycle graph $C_{3n}$. Suppose there is a partition of $V$ into sets of $3$, i.e. $V=\cup_{k=1}^{n}{V_k}$ where $|V_k|=3$ for $k$ in $1..n$.

QUESTION: Is it possible to find an independent set of $V$ with exactly one vertex from each $V_k$?

By the Lovasz Local Lemma, it's possible if the $3$ is replaced with some larger number, say, $11$.

  • $\begingroup$ How could this be possible, I mean what if three vertices in a partition were adjacent to each other? Are there any conditions on the partitions $V_k$? $\endgroup$ – vidyarthi May 14 '19 at 11:21
  • $\begingroup$ If they are mutually adjacent, it follows that $n=1$, so it is still possible (just choose any vertex). $\endgroup$ – LeechLattice May 14 '19 at 11:26
  • $\begingroup$ any vertex is adjacent to exactly two other vertices, as there are $3$ vertices, therefore one vertex from any part would be definitely non-adjacent to at least one vertex from any other part. Thus, we can choose one vertex from each part which are independent of each other $\endgroup$ – vidyarthi May 14 '19 at 11:32
  • 2
    $\begingroup$ @vidyarthi I don't think that's a proof. As vertices are added to the independent set, you can come to a part where each of the three vertices is adjacent to a vertex already in the independent set. $\endgroup$ – Brendan McKay May 14 '19 at 13:13

The answer is yes, via a stronger proposition: for each part in the partition, add edges between the vertices the part contains; the question now is, can you vertex-3-color the resulting graph? This is the well-known cycle plus triangles problem, originally posed by Erdos and solved by Fleischner and Stiebitz using the Alon-Tarsi theorem, and later again by Sachs (inductively), affirmatively. The proofs are far from trivial or easy (I happen to like the inductive proof).

So to answer your question, just pick a color class ...

| cite | improve this answer | |
  • 2
    $\begingroup$ Quoting from the abstract of Michael R. Fellows's paper "Transversals of Vertex Partitions in Graphs" (SIAM J. Discrete Math., 3(2), 206–215): This paper studies graph properties of the following forms: For every partition of the vertex set that satisfies an upper (or lower) bound on the number of elements in each partition class, there is a transversal of the partition that is an independent (or dominating) set. $\endgroup$ – Seva May 14 '19 at 19:51
  • 1
    $\begingroup$ @Seva Thanks for the edit and the comment $\endgroup$ – EGME May 14 '19 at 20:20

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.