16 citations · 48 across the 24 of their papers we have counts for
3 papers · 2 filters
Finding a sun in building-free graphs
Elaine M. Eschen, Chinh T. Hoang, Jeremy P. Spinrad +1
Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete. We show that whether a building-free graph contains a sun can be decided in O(min$\{m{n^3},…
On graphs without a C4 or a diamond
Elaine M. Eschen, Chinh T. Hoang, Jeremy P. Spinrad +1
We consider the class of (C4, diamond)-free graphs; graphs in this class do not contain a C4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for…
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…