Results 1 to 3 of 3

Math Help - graph theory, chromatic number relation

  1. #1
    Member Jason Bourne's Avatar
    Joined
    Nov 2007
    Posts
    132

    graph theory, chromatic number relation

    Let G be a simple graph with v vertices and every vertex of degree d. Show that \chi (G) \geq \frac{v}{(v-d)}

    where  \chi (G) is the chromatic number, the least k for which the graph G is k-colourable.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Jason Bourne View Post
    Let G be a simple graph with v vertices and every vertex of degree d. Show that \chi (G) \geq \frac{v}{(v-d)}

    where  \chi (G) is the chromatic number, the least k for which the graph G is k-colourable.
    Remark: let V be the set of verices of G. if A \subseteq V has this property that no two vertices in A are adjacent, then |A| \leq v-d. this is because if |A| \geq v-d+1, then |V-A| \leq d-1 and so

    a vertex in A can be adjacent to at most d-1 vertices, which contradicts d regularity of G.

    now label the colors with 1, 2, \cdots , \chi(G), and for any 1 \leq k \leq \chi(G) let A_k be the set of all vertices in V colored k. then clearly \bigcup_{k=1}^{\chi(G)} A_k=V and for any i \neq j: \ A_i \cap A_j = \emptyset. also by the above
    remark |A_k| \leq v-d, for all 1 \leq k \leq \chi(G). therefore: v=|V|=\sum_{k=1}^{\chi(G)} |A_k| \leq (v-d) \chi(G). Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    there's a lower bound for the chromatic number of any simple graph, which generalizes your problem and the proof is just a simple modification of the proof i gave you:

    let G be any simple graph, V the set of vertices of G, and W the largest subset of V with this property that no two vertices in W are adjacent. then: \chi(G) \geq \frac{|V|}{|W|}.
    Last edited by NonCommAlg; May 6th 2009 at 05:41 AM. Reason: lower not upper bound! haha
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  2. Replies: 0
    Last Post: February 12th 2011, 06:02 AM
  3. Chromatic number and graph complements
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2009, 12:51 PM
  4. Chromatic Polynomial in Graph Theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 01:45 PM
  5. Chromatic Number of a line graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2009, 07:29 PM

Search Tags


/mathhelpforum @mathhelpforum