Complexity Results in Graph Fall-Coloring

Graph fall-coloring is the partition of the vertices of a graph into independent dominating sets. A problem is in NP if its solutions can be verified in polynomial time. A problem is NP-complete if it is in NP and every problem in NP can be efficiently converted to an instance of this problem. In this talk, we will look at some NP-complete problems relating to graph fall-coloring. We will look at families of graphs for which some question of fall-colorability is NP-complete to answer. We will also look at families of graphs for which finding two disjoint independent dominating sets is NP-complete. Finally, we will look at some smaller results on the potential for fall-colorability of some families of graphs. This talk is a continuation from the talk of last semester on the same general topic; however, no knowledge of the results and ideas previously covered will be required nor assumed. Joint work with Juho Lauri (Nokia Bell Labs, Ireland)

Event Topic

Discrete Applied Math Seminar