Results 1 to 7 of 7

Thread: Graph Coloring Problem

  1. #1
    Newbie
    Joined
    Apr 2016
    From
    Argentina
    Posts
    7

    Graph Coloring Problem

    Let G be the graph whose vertices are the 1225 squares of a square board with 35 rows and 35 columns. Two vertices are neighbors if placing a dame in each of the lockers the ladies attack each other. (That is, if the boxes are in the same row, column or diagonal, where diagonal is not necessarily one of the main diagonals). Prove that χ (G) = 35.

    Dame is equivalent to a queen in English.
    Last edited by Plato; Mar 31st 2017 at 02:51 PM. Reason: translation
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,608
    Thanks
    301

    Re: Graph Coloring Problem

    Quote Originally Posted by dantopa View Post
    Two vertices are neighbors if placing a dame in each of the lockers the ladies attack each other.
    Huh? vertices? lockers? pissed off ladies?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2016
    From
    Argentina
    Posts
    7

    Re: Graph Coloring Problem

    It's talking about draughts game, in spanish is called "damas" (dames). Sorry I have used the translator directly, and lockers refers to box.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,608
    Thanks
    301

    Re: Graph Coloring Problem

    Well, suggest you get an English girlfriend...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2016
    From
    Argentina
    Posts
    7

    Re: Graph Coloring Problem

    Here is the problem again:
    Let G be the graph whose vertices are the 1225 squares of a square board with 35 columns and 35 rows. Two vertices are neighbors if putting a queen on each of the squares the queens attack mutually (that means when the squares are on the same row, column or diagonal, where diagonal is not necessarily one of the main diagonals). Prove that X(G) = 35 (this means the chromatic number)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Graph Coloring Problem

    Check out this article.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2016
    From
    Argentina
    Posts
    7

    Re: Graph Coloring Problem

    Perfect! Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph coloring/labeling
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 23rd 2014, 11:05 PM
  2. graph coloring
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 2nd 2011, 02:30 AM
  3. Graph coloring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 2nd 2010, 11:49 AM
  4. Graph coloring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 1st 2010, 10:06 PM
  5. Cooperative graph coloring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Jan 1st 2010, 02:30 AM

Search Tags


/mathhelpforum @mathhelpforum