<p>χ(G) + α(G) &lt;= n+1
where n is the number of vertices of the graph.</p>

<p>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</p>

<p>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)</p>

<p>Now both increase, showing that n+2>=χ(G*) + α(G*)
Thus χ(G*) + α(G*) &lt;= |G*| + 1
QED
The bound is tight for complete graphs and null graphs.</p>

CC BY-SA 3.0
2015-04-21T08:02:57.760Z
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$.
Louis Esperet
CC BY-SA 3.0
2015-04-18T08:15:16.723Z
2015-04-18T08:15:16.723Z
Arvind Ravi
<p>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 <em>no</em>, there is no such function.</p>

<p>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.</p>

<p>(See Section 3.1 of my thesis for more details. <a href="http://www.columbia.edu/~ak3074/papers/phdthesis-compact.pdf">http://www.columbia.edu/~ak3074/papers/phdthesis-compact.pdf</a>)</p>

CC BY-SA 3.0
2011-06-13T13:55:21.517Z
The file is damaged and could not be repaired....
James King
CC BY-SA 3.0
2016-03-19T13:59:01.873Z
link does not work anymore.
oerpli
CC BY-SA 3.0
2011-06-13T12:05:24.483Z
2011-06-13T12:05:24.483Z
Andrew D. King
<p>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$?</p>

CC BY-SA 3.0
2011-06-13T07:54:56.053Z
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$?
James King
CC BY-SA 3.0
2011-06-13T13:00:48.160Z
Sorry, f($\Delta$) indeed.
Regularity
<graph-theory><co.combinatorics><graph-colouring>
Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?
Regularity
# Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?

(Asked by: username_0 on 2011-06-12)

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$?

**Tags:** graph-theory, co.combinatorics, graph-colouring
> **Comments:**
> **username_1**: 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$?  
> **username_0**: Sorry, f($\Delta$) indeed.  

---

## 2 answers

### Answer by username_4 on 2011-06-13. Score: 11 | Accepted answer

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>)

> **Comments:**
> **username_1**: The file is damaged and could not be repaired....  
> **username_5**: link does not work anymore.  

---

### Answer by username_2 on 2015-04-18. Score: 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.

> **Comments:**
> **username_3**: 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$.  

---

