1
$\begingroup$

Could you give an example or a proof for a graph that has no triangles but still has chromatic number $\chi(G) \ge n$, where $n \gt 3$ is the number of vertices? This is from coloring of a graph.

The only way I can think about it is in terms of complete graph $K_n$, but that has triangles and its chromatic number is $\chi(K_n) \ge n$. But can you give an example for a graph that is not complete and still has $\chi(G) \ge n$?

$\endgroup$

2 Answers 2

3
$\begingroup$

An upper bound for chromatic number is $\chi(G) \le \Delta(G)+1$ (see Greedy coloring). And we know that for any simple graph $G$, we have $\Delta(G) \le n-1$ (Note that if $G$ is not simple, we can consider its condensation by removing parallel edges as they don't affect chromatic number). Thus, we have $\chi(G) \le n$. So, it is not hard to see that $\chi(G) = n$ is possible only when we have $G = K_n$. But, as you noticed, this is not a triangle-free graph for $n \ge 3$.

However, if you are not restricting yourself with number of vertices, I recommend you to see Mycielski Graph as they can generate a graph with any chromatic number you want and they are always triangle-free.

$\endgroup$
0
1
$\begingroup$

I assume that by $n$ you mean the number of vertices. If a graph is not complete then there is a pair of vertices with no edge between them, color them in the same color and all of the other vertices in their own unique colors to obtain an $(n-1)$-coloring. So a graph that has chromatic number $\ge n$ is complete. A complete graph can still contain no triangle, as long as it has less than 3 vertices :). If it has 3 or more then take any 3 of them to form a triangle.

$\endgroup$

You must log in to answer this question.

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