Shenwei Huang (SFU)
21/03/14 12:00 Talks
Coloring Graphs without Induced Paths and Cycles
Speaker:
Shenwei Huang (Simon Fraser University, Computing Science)
Abstract:
Let P_t and C_l denote the path on t and l vertices, respectively. It is well known that k-coloring is NP-complete for P_t-free graphs, for most combinations of values of k and t. In this talk, we study the complexity of k-coloring (P_t,C_l)-free graphs. We prove that for most values of k,l,t, the problem is still NP-complete. On the positive side, we develop a linear time certifying algorithm for 3-coloring and 4-coloring (P_6,C_4)-free graphs by providing a complete finite list of minimal non-k-colorable (P_6,C_4)-free graphs for k=3,4. For higher value of k, it seems impossible to provide such a list. Yet, we show that the number of minimal non-k-colorable (P_6,C_4)-free graphs is always finite.
Joint work with Pavol Hell.
Date:
Friday, March 21, 2014
Time:
12:00 pm - 13:00 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Shenwei Huang (Simon Fraser University, Computing Science)
Abstract:
Let P_t and C_l denote the path on t and l vertices, respectively. It is well known that k-coloring is NP-complete for P_t-free graphs, for most combinations of values of k and t. In this talk, we study the complexity of k-coloring (P_t,C_l)-free graphs. We prove that for most values of k,l,t, the problem is still NP-complete. On the positive side, we develop a linear time certifying algorithm for 3-coloring and 4-coloring (P_6,C_4)-free graphs by providing a complete finite list of minimal non-k-colorable (P_6,C_4)-free graphs for k=3,4. For higher value of k, it seems impossible to provide such a list. Yet, we show that the number of minimal non-k-colorable (P_6,C_4)-free graphs is always finite.
Joint work with Pavol Hell.
Date:
Friday, March 21, 2014
Time:
12:00 pm - 13:00 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby