Results 1 to 3 of 3

Thread: 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 $\displaystyle \chi (G) \geq \frac{v}{(v-d)}$

    where$\displaystyle \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 $\displaystyle \chi (G) \geq \frac{v}{(v-d)}$

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

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

    now label the colors with $\displaystyle 1, 2, \cdots , \chi(G),$ and for any $\displaystyle 1 \leq k \leq \chi(G)$ let $\displaystyle A_k$ be the set of all vertices in $\displaystyle V$ colored $\displaystyle k.$ then clearly $\displaystyle \bigcup_{k=1}^{\chi(G)} A_k=V$ and for any $\displaystyle i \neq j: \ A_i \cap A_j = \emptyset.$ also by the above
    remark $\displaystyle |A_k| \leq v-d,$ for all $\displaystyle 1 \leq k \leq \chi(G).$ therefore: $\displaystyle 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 $\displaystyle G$ be any simple graph, $\displaystyle V$ the set of vertices of $\displaystyle G,$ and $\displaystyle W$ the largest subset of $\displaystyle V$ with this property that no two vertices in $\displaystyle W$ are adjacent. then: $\displaystyle \chi(G) \geq \frac{|V|}{|W|}.$
    Last edited by NonCommAlg; May 6th 2009 at 04: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: Nov 15th 2011, 09:59 AM
  2. Replies: 0
    Last Post: Feb 12th 2011, 05:02 AM
  3. Chromatic number and graph complements
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 30th 2009, 11:51 AM
  4. Chromatic Polynomial in Graph Theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 29th 2009, 12:45 PM
  5. Chromatic Number of a line graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2009, 06:29 PM

Search Tags


/mathhelpforum @mathhelpforum