1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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