- #1

titaniumx3

- 53

- 0

## Homework Statement

Prove that every triangle-free graph G on

*n*vertices has chromatic number at most [tex]2\sqrt{n}+1[/tex].

## Homework Equations

The chromatic number of a graph G is the smallest number of colors needed to color the vertices of a graph so that no two adjacent vertices share the same color.

Trinagle-free graph means that there are no loops of length 3 contained in the graph.

## The Attempt at a Solution

For a triangle free graph G on*n*vertices, we know that for a vertex

*x_1*, the neighbourhood of

*x_1*forms an independent set (i.e. there are no edges between any two vertices); otherwise their would be triangles.

Therefore, all vertices of the neighbourhood

*N(x_1)*can be coloured with a single colour, say "1".

Now suppose we take the subgraph

*H*where

*H = G - N(x_1)*and take another vertex

*x_2*in

*H*, then the neighbourhood of

*x_2*in

*H*is also an independent set, hence it can be coloured with a single colour, say "2". Note that the colour may not necessarily be "1" since there may be edges between the neighbourhoods of

*x_1*and

*x_2*.

If we repeat this process and define a new subgraph as before, then we can define another neighbour hood of a particular vertex and colour it with "3" and so on. Now, we can minimise the number of colours used in this process by letting the vertices

*x_1, x_2, x_3, ... , x_r*(for some

*r*) be the the vertex of maximum degree at each step. Hence at each step, in creating each subgraph we will discard a number of vertices amounting to the maximum degree of the the preceeding graph.

My problem now is that I can't figure out how many steps we can take and express it in terms of

*n*.

Last edited: