Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Question about triangle free graphs

  1. Feb 18, 2008 #1
    1. The problem statement, all variables and given/known data

    Prove that every triangle-free graph G on n vertices 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 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: Feb 18, 2008
  2. jcsd
  3. Feb 18, 2008 #2
    Anyone? :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook