Consider an connected undirected graph $G$ with $n$ vertices and maximum degree $\Delta$. Assume $G$ contains a maximum independent set of size $k$. Is there any relation between the chromatic number $\chi(G)$ and $k$? Say of the form $\chi(G)\le f(\Delta)\frac{n}{k}$ for some function $f$?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ What is $d$? I'm assuming you want this function $f(d)$ to be independent of $\Delta$? If so, how can $\Delta$ help us? If not, do you want something better than the trivial bound of $\Delta+1$? $\endgroup$– James KingJun 13, 2011 at 7:54
-
$\begingroup$ Sorry, f($\Delta$) indeed. $\endgroup$– RegularityJun 13, 2011 at 13:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Obviously if $f(\Delta)=2\Delta$ then the bound holds. However, I doubt this is what you meant. Perhaps you meant $\chi(G) \leq f(\frac n k)$, in which case the answer is no, there is no such function.
Let $\alpha$ be the size of a maximum independent set in $G$. Then it is easy to see that the fractional chromatic number satisfies the bound $\chi_f(G)\geq \frac n \alpha$. One such example is the Kneser graph $K_{kb:b}$ for fixed integers $k$ and $b$. This graph has fractional chromatic number $k = \frac n\alpha$, and chromatic number $(k-2)b+2$. So for fixed $k$ and large $b$ the answer is no.
(See Section 3.1 of my thesis for more details. http://www.columbia.edu/~ak3074/papers/phdthesis-compact.pdf)
-
2$\begingroup$ The file is damaged and could not be repaired.... $\endgroup$ Jun 13, 2011 at 13:55
-
$\begingroup$
$\endgroup$
1
χ(G) + α(G) <= n+1 where n is the number of vertices of the graph.
Proof by Induction: Notice that a single vertex has χ(G) + α(G) = 2. Add each vertex one by one. Notice that by adding a single vertex you can only increase them by one. By doing this, we convert G into G*. Say the new vertex v is connected to vertices 1 through r of our previous G and not connected to the vertices r+1 through n. For the inequality to be disturbed according to our induction hypothesis both have to be increased at one point
For χ(G) to increase, the 1 through r vertices, v is connected to needs r colours in any proper colouring of G. Thus |r| >= χ(G). Also the maximum independent set that v must be part of has to be contained in G - r. Therefore |G - r| >= α(G) Adding the two inequalities gets you |G| = n >= χ(G) + α(G)
Now both increase, showing that n+2>=χ(G*) + α(G*) Thus χ(G*) + α(G*) <= |G*| + 1 QED The bound is tight for complete graphs and null graphs.
-
1$\begingroup$ I think that your statement has an obvious (non-inductive) proof. Take a maximal independent set $S$ in your graph, color all the vertices of $S$ with color 1, and all the remaining vertices of $G$ with pairwise distinct colors. You obtain a coloring of $G$ with $n-\alpha(G)+1$ colors, so $\chi(G)+\alpha(G)\leq n+1$. $\endgroup$ Apr 21, 2015 at 8:02