Games and graphs

Well-covered graphs: Divide-and-conquer is a well-tried and useful approach to hard problems. On the other hand, well-covered graphs have the property that hard problems (like scheduling jobs or examinations) are easy: the hard part is recognizing when a graph is well-covered. A labeling approach based on recognizing when two `jobs' cannot be scheduled at the same time partitions the graph into well-covered subgraphs that allows an easy but good starting point from which to schedule all the `jobs'.`Decontaminating a network' can mean catching intruders to cleaning up chemical or biological contamination. Of particular interest for this proposal is the situation where the network has to be cleaned regularly because of a slow growing contaminant which may be anything from algae in the pipes of a power plant to dust in a house. Combinatorial games are two person games of perfect information and without chance elements. The theory provides techniques for determining who can win from a game position and how. While ad hoc techniques for such analysis are as old as humanity, the modern theory employs more powerful and general tools such as the notion of a game-theoretic value and reduced canonical form. From a mathematical standpoint, these techniques can be brought to bear to completely solve a wide variety of games.