0
$\begingroup$

I'm looking for interesting examples of questions in discrete math that can be proved using graph colorings (as, for example existence of a particular division of people into $k$ distinct groups with given conditions, using, in the proof, that an associated graph is $k$-colorable). I need those example for a basic course in discrete math for undergraduates. Thanks in advance for any help.

  • 0
    @M.B.: That's a nice one, thanks.2012-06-12

1 Answers 1

1

Timothy Gowers discusses one such example 7:10 out in this clip and it continues in part 6.

Summary: You have seven candidates and eight papers. Each candidate takes either two or three papers and cannot take two at the same time. Can this be done in three sittings? Form a graph with eight nodes, each representing a paper, and draw an edge between two nodes if they cannot be performed in the same sitting (i.e. at least one student is doing both papers). Then three sittings will be sufficient if and only if there exists a coloring of the graph with three colors such that no two nodes of the same color are connected by an edge.

  • 0
    +1. As I commented before, I like this example, but I don't want to accept an answer now because I would like to see some additional examples.2012-06-12