- #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: