12 citations · 12 across the 2 of their papers we have counts for
2 papers
cs.DM2009★ 12 cited
A certifying algorithm for 3-colorability of P5-free graphs
Daniel Bruce, Chinh T. Hoang, Joe Sawada
We provide a certifying algorithm for the problem of deciding whether a P5- free graph is 3-colorable by showing there are exactly six finite graphs that are P5-free and not 3-colo…
cs.DM2006
k-Colorability of P5-free graphs
C. T. Hoang, J. Sawada, X. Shu
A polynomial time algorithm that determines for a fixed integer k whether or not a P5-free graph can be k-colored is presented in this paper. If such a coloring exists, the algorit…