# questions on implications Babais quasi P time graph isomorphism result

Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs.

• based on the proof, does this mean now that if Johnson graphs can be recognized in P-time, then graph isomorphism is also in P-time?

• is the proof also essentially showing that recognizing Johnson graphs can be done in at least quasipolynomial time? and presumably this improved on prior results... what was known previously, has it changed? has the recognition time for Johnson graphs been studied in particular? is it now likely to be an area of focus after the proof, or might future research go in some other direction?

[1] Graph isomorphism vanquished again / Klarreich, Quanta magazine