# Thread: Graph Coloring Problem

1. ## 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.

2. ## Re: Graph Coloring Problem

Originally Posted by dantopa
Two vertices are neighbors if placing a dame in each of the lockers the ladies attack each other.
Huh? vertices? lockers? pissed off ladies?

3. ## 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.

4. ## Re: Graph Coloring Problem

Well, suggest you get an English girlfriend...

5. ## 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)

6. ## Re: Graph Coloring Problem

Check out this article.

7. ## Re: Graph Coloring Problem

Perfect! Thanks