Isomorphism Testing for Graphs Excluding Small Topological Subgraphs

Abstract: We give an isomorphism test that runs in time

n^{o p e r a t o r n a m e p o l y l o g (h)}

on all

n

-vertex graphs excluding some

h

-vertex vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time

n^{o p e r a t o r n a m e p o l y l o g (n)}

(Babai, STOC 2016) and

n^{f (h)}

for some function

f

(Grohe and Marx, SIAM J. Comp., 2015). Our result also unifies and extends previous isomorphism tests for graphs of maximum degree

d

running in time

n^{o p e r a t o r n a m e p o l y l o g (d)}

(FOCS 2018) and for graphs of Hadwiger number

h

running in time

n^{o p e r a t o r n a m e p o l y l o g (h)}

(FOCS 2020).

This page was built for publication: Isomorphism Testing for Graphs Excluding Small Topological Subgraphs