(Center for Discrete Math and Theoretical Computer Science (DIMACS) and Bell Labs)
Coloring and List-coloring of Graphs
Abstract. Graph coloring is the standard way to model many scheduling problems, and it has applications in areas such as register allocation, radio frequency assignment, secret sharing, and even Sudoku puzzles. We will review some major results in graph coloring and one of its popular variants, list-coloring. I will then discuss open problems in these areas and progress that I have made on them.