6
$\begingroup$

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$.

Improve this question
$\endgroup$
4
  • $\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
    Commented May 14, 2019 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
    Commented May 14, 2019 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
    Commented May 14, 2019 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
    Commented May 14, 2019 at 13:13

1 Answer 1

Reset to default
5
$\begingroup$

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 ...

Improve this answer
$\endgroup$
2
  • 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
    Commented May 14, 2019 at 19:51
  • 1
    $\begingroup$ @Seva Thanks for the edit and the comment $\endgroup$
    – EGME
    Commented May 14, 2019 at 20:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .