Let $N>2$ be a positive integer and $G$ be a simple graph satisfies:

  1. the maximal degree of $G$ is $N$
  2. the clique number of $G$ is $N$.

I want to ask if there exists a vertex independent set $I$ in $V(G)$ such that for every $N$-order complete subgraph $H$ of $G$, the intersection of $I$ and $V(H)$ is not empty. If not, please give a counterexample.

  • $\begingroup$ First,if $I$ is empty,$I$ does not satisfes "for every $N$ -order complete subgraph $H$ of $G$, the intersection of $I$ and $V$($H$) is not empty"!Second,as you said,if the intersection of $I$ and $V$($H$) is empty,how do you know the vertex in $I$ is not adjacent to any vertex of $H$? $\endgroup$ – user40096 Sep 28 '13 at 10:29
  • $\begingroup$ You did not see my question carefully!The maximal degree of $G$ is $N$,but for any $N$-order complete subgraph $H$ of $G$,the degree of every vertex of $H$ is $N$-1. $\endgroup$ – user40096 Sep 28 '13 at 13:58
  • $\begingroup$ one counter example for $N=2$ would be an odd cycle. For $N\ge 3$, I am not quite sure. $\endgroup$ – Flo Pfender Sep 28 '13 at 14:42
  • $\begingroup$ @user40096: I overlooked the difference between $N$ and $N-1$. My earlier comments removed. $\endgroup$ – Seva Sep 28 '13 at 17:00

If $G$ is an odd cycle (as commented above), the answer is no. If it's an $(n+1)$-clique, it meets your degree condition but not your condition on the clique number. And if it's neither a clique nor an odd cycle, then by Brooks' theorem, it has an $n$-coloring, all of whose color classes are independent sets that meet every $n$-clique.

| cite | improve this answer | |
  • $\begingroup$ My condition has "$N>2$",so $G$ is not an odd cycle.And for the rest of your answer,it is right,thank you very much! $\endgroup$ – user40096 Sep 29 '13 at 2:00

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.