2
$\begingroup$

Let $k\geq2$ be an integer, a graph $G=(V,E)$ is called $k$-partite if $V$ admits a partition into $k$ classes such that every edge of $G$ has its ends in different classes: vertices in the same class must not be adjacent.

Now let $G=(V,E)$ be $k$-partite and $V_1,V_2,\cdots,V_k$ be the $k$ classes into which $V$ Is partitioned such that:

$(1)\Delta (G)=2;$

$(2)|V_i|=3,i=1,2,\cdots,k;$

$(3)$For any $1\leq i\neq j\leq k$, there does not exist $u\in V_i$ and $v,w\in V_j$ such that $u$ are adjacent with both $u$ and $w$.

I want to ask if I can choose $v_i$ from $V_i, i=1,2,\cdots,k$ such that $\{v_1,v_2,\cdots,v_k\}$ is an independent set in $G$.

Improve this question
$\endgroup$
4
  • $\begingroup$ Lovely problem! I will think first about the (possibly trivial and uninteresting) variant $\Delta(G)=1$ and $|V_i|=2$. $\endgroup$
    – Dominic van der Zypen
    Commented Mar 3, 2015 at 9:16
  • $\begingroup$ It is right when $\Delta (G)=1$ and $\mid V_i\mid=2$,you can use Hall's marriage theorem. $\endgroup$
    – user40096
    Commented Mar 3, 2015 at 14:21
  • $\begingroup$ Such an independent set is called an "independent transversal". There is a large literature on this topic, although I have never seen the $\Delta(G)=2$ assumption in this setting. $\endgroup$
    – David Wood
    Commented Mar 4, 2015 at 23:01
  • $\begingroup$ It is a theorem of Haxell that an independent transversal exists in general when $\Delta(G)=k$ and $|V_i| = 2k$, (see here link.springer.com/article/10.1007/BF01793010 or here link.springer.com/article/10.1007/s00493-007-2086-y). By the way assumption (3) would be necessary. Take three disjoint copies of $C_4$ and colour the vertices in circular order 1,2,1,2 and 3,4,3,4 and 1,3,2,4 respectively. This graph has no independent set meeting all four colours. $\endgroup$
    – Katie Edwards
    Commented Mar 5, 2015 at 15:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .