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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.