Complexity Results in Graph Fall-Colouring
Host
Department of Applied Mathematics
Speaker
Christodoulos Mitillos
Department of Applied Mathematics, Illinois Institute of Technology
Description
Graph fall-colouring 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 in graph fall-colouring. We will review the general problems kFC, FC, FKC, and FEDk, known to be NP-complete for general graphs. We will also look at specific families of graphs for which some instance of kFC is NP-complete.
Joint work with Juho Lauri (Nokia Bell Labs, Ireland).
Event Topic
Discrete Applied Math Seminar