3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Sep 28, 2013 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
    Commented Sep 28, 2013 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
    Commented Sep 28, 2013 at 14:42
  • $\begingroup$ @user40096: I overlooked the difference between $N$ and $N-1$. My earlier comments removed. $\endgroup$
    – Seva
    Commented Sep 28, 2013 at 17:00

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Sep 29, 2013 at 2:00

You must log in to answer this question.

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