Induced Minor Free Graphs: Isomorphism and Clique-Width

被引：0
作者：
Rémy Belmonte
Yota Otachi
Pascal Schweitzer
机构：
[1] University of Electro-Communications,
[2] Japan Advanced Institute of Science and Technology,undefined
[3] RWTH Aachen University,undefined
来源：
Algorithmica | 2018年 / 80卷
关键词：
Induced minor; Graph isomorphism; Clique-width;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph.
引用
收藏
页码：29 / 47
页数：18
相关论文
共 50 条
[1]  
Błasiok J(2015)Induced minors and well-quasi-ordering Electr. Notes Discrete Math. 49 197-201
[2]  
Kamiński M(1981)On testing isomorphism of permutation graphs Networks 11 13-21
[3]  
Raymond J-F(2005)On the relationship between clique-width and treewidth SIAM J. Comput. 34 825-847
[4]  
Trunck T(2014)Clique-width and edge contraction Inf. Process. Lett. 114 42-44
[5]  
Colbourn CJ(2000)Linear time solvable optimization problems on graphs of bounded clique-width Theory Comput. Syst. 33 125-150
[6]  
Corneil DG(2000)Upper bounds to the clique width of graphs Discrete Appl. Math. 101 77-114
[7]  
Rotics U(2016)Classifying the clique-width of Discrete Appl. Math. 200 43-51
[8]  
Courcelle B(2016)-free bipartite graphs Comput. J. 59 650-666
[9]  
Courcelle B(1995)Clique-width of graph classes defined by two forbidden induced subgraphs Algorithmica 13 266-282
[10]  
Makowsky JA(2000)The complexity of induced minors and related problems Int. J. Found. Comput. Sci. 11 423-443
12345