Results 1 to 2 of 2

Math Help - Graph Theory- Edge Colouring

  1. #1
    Len
    Len is offline
    Member
    Joined
    Mar 2008
    Posts
    93
    Thanks
    1

    Graph Theory- Edge Colouring

    Let G be a simple graph with n vertices and m edges.

    Show that if n is odd and m > ((n-1)*Δ(G))/2 , then χ′(G) = Δ(G)+1


    I'm having trouble with this problem, I know Vizing theorem and it states that in order for χ′(G) = Δ(G)+1 to be true G must be class 2.

    How do I show G is class 2? Class 2 Graph -- from Wolfram MathWorld

    Δ(G) is the maximum degree of G.

    Or is there an easier way.

    Thanks and plus rep!

    EDIT: It's not enough to show that if it would hold for one example under the criteria it would hold for all is it? I don't think so
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    well graphs are either class 1 or class 2, so all you have to show is that  \chi'(G) \neq \Delta(G)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Edge colouring in K_n
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 28th 2010, 11:52 PM
  2. [SOLVED] graph vertex colouring
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 2nd 2010, 10:46 AM
  3. Graph theory - colouring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 17th 2010, 08:26 PM
  4. colouring vertices in graph theory
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 3rd 2009, 03:53 PM
  5. Graph Theory - Edge Cut / Connectivity
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: July 6th 2009, 04:52 AM

Search Tags


/mathhelpforum @mathhelpforum