Results 1 to 2 of 2

Math Help - Paths in Coloured Graphs

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    15

    Paths in Coloured Graphs

    Suppose \chi(G)=k and c:V(G) \rightarrow \{1,\ldots,k\} is a proper k-colouring of G. Must there be a path x_1 \ldots x_k in G with c(x_i)=i for each i?

    I've been trying to find a counter-example without any luck (but on the other hand can't come up with a proof either...)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member nimon's Avatar
    Joined
    Sep 2009
    From
    Edinburgh, UK
    Posts
    64
    Take a look at the Gallai-Roy-Vitaver theorem and its corollaries. Apparently, a proof can be found in this article but you might be better to find the original somewhere.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Augmenting paths
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 17th 2009, 05:55 AM
  2. Help on Graphs and Paths
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 26th 2009, 04:29 AM
  3. Simple Graphs and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 10:10 AM
  4. coloured faces of an octahedron
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 18th 2008, 05:51 PM
  5. How many paths...?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 14th 2008, 08:54 AM

/mathhelpforum @mathhelpforum