(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Prove that every triangle-free graph G onnvertices has chromatic number at most [tex]2\sqrt{n}+1[/tex].

2. Relevant 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.

3. The attempt at a solution

For a triangle free graph G onnvertices, we know that for a vertexx_1, the neighbourhood ofx_1forms an independent set (i.e. there are no edges between any two vertices); otherwise their would be triangles.

Therefore, all vertices of the neighbourhoodN(x_1)can be coloured with a single colour, say "1".

Now suppose we take the subgraphHwhereH = G - N(x_1)and take another vertexx_2inH, then the neighbourhood ofx_2inHis 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 ofx_1andx_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 verticesx_1, x_2, x_3, ... , x_r(for somer) 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 ofn.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Question about triangle free graphs

**Physics Forums | Science Articles, Homework Help, Discussion**