Chepoi showed that every breadth /rst search of a bridged graph produces a cop-win ordering of the graph. We note here that Chepoi’s proof gives a simple proof of the theorem that G is bridged if and only if G is cop-win and has no induced cycle of length four or /ve, and that this characterization together with Chepoi’s proof reduces the time complexity of bridged graph recognition. Speci/cally, we show that bridged graph recognition is equivalent to ( C4 ;C 5)-free
['Van Bang Le', 'Jeremy P. Spinrad']
Consequences of an algorithm for bridged graphs