Consequences of an algorithm for bridged graphs

Chepoi showed that every breadth first 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 five, and that this characterization together with Chepoiʹs proof reduces the time complexity of bridged graph recognition. Specifically, we show that bridged graph recognition is equivalent to (C4,C5)-free graph recognition, and reduce the best known time complexity from O(n4) to O(n3.376).