Shenwei Huang (SFU)

Coloring Graphs without Induced Paths and Cycles
Shenwei Huang (Simon Fraser University, Computing Science)


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.


Friday, March 21, 2014


12:00 pm - 13:00 pm

TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby