Colored-domination and colored-independence in graphs
Dr. Peter Slater
Department of Mathematical Sciences and Department of Computer Science, UAH
October 19, 2007
202 Madison Hall
3:00 - 4:00 (Refreshments at 2:30 in 201 Madison Hall)
For the class of colored problems under consideration, the vertices /nodes of a graph are partitioned into color classes. Each node can represent a person, an object to be stored, or a job to be completed. Problems considered include forming committees or job scheduling under various constraints. Typical problems have constraints that involve people/jobs that can not serve together or be scheduled simultaneously. Further constraints might involve people/jobs that must be placed/executed together. Edges of the graph represent the conflicts, and the color classes indicate the simultaneity constraints.
A mixture of mathematics, operations research and computer science will be presented. In particular, it will be shown that the colored-independence and colored-domination problems are NP-complete even when the graphs considered are restricted to be simply (as simple as possible a case as) the paths, and even when rather severe restrictions are placed on the possible color classes.
- Hits: 95