Showing cs.DMShow all
3 papers · 1 filter
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.DM2008
Asteroids in rooted and directed path graphs
Kathie Cameron, Chinh Hoàng, Benjamin Lévêque
An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central r…
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…