Complexity of k-coloring (subdivided claw)-free graphs with bounded diameter.

Abstract: During the last decades, there has been a lot of research on the computational complexity of k-coloring in H- free graphs when H is a linear forest. It is known that  k-coloring $K_{1,3}$ (claw) free graphs is NP-complete for $k\geq 3$.In this talk, we will study the techniques used by Barnaby Martin, Daniël Paulusma and Siani Smith in 2021 to generalize this result for $K^{r}_{1,3}$ (subdivided claw) free graphs with bounded diameter.

Posted on Apr 24, 2023 in Seminario de Grafos, Seminars