Towards an isomorphism dichotomy for hereditary graph classes
type: Item
instance of: scholarly article
title: Towards an isomorphism dichotomy for hereditary graph classes
zbMATH Open document ID: 1380.68232
author: P. Schweitzer
published in: Theory of Computing Systems
publication date: 2018-02-01T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/4951/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 6833241
zbMATH Keywords: graph isomorphism
zbMATH Keywords: modular decomposition
zbMATH Keywords: bounded color valence
zbMATH Keywords: reductions
zbMATH Keywords: forbidden induced subgraphs
MaRDI profile type: Publication
OpenAlex ID: W1663329006
cites work: Colored hypergraph isomorphism is fixed parameter tractable
cites work: Q3912033
cites work: Q4871775
cites work: Graph isomorphism in quasipolynomial time [extended abstract]
cites work: Dominating cliques in \(P_ 5\)-free graphs
cites work: Distance-hereditary graphs
cites work: On the structure of (\(P_{5}\),\,gem)-free graphs
cites work: Q4170760
cites work: Q5747380
cites work: Colouring of graphs with Ramsey-type forbidden subgraphs
cites work: A nonfactorial algorithm for testing isomorphism of two graphs
cites work: List coloring in the absence of two subgraphs
cites work: Structure theorem and isomorphism test for graphs with excluded topological subgraphs
cites work: Q4366883
cites work: Q4790399
cites work: A survey of the algorithmic aspects of modular decomposition
cites work: Conflict Propagation and Component Recursion for Canonical Labeling
cites work: Q4273947
cites work: From Invariants to Canonization in Parallel
cites work: Q4448764
cites work: Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
cites work: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
cites work: A decidability result for the dominating set problem
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Q3670594
cites work: A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
cites work: Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes
cites work: Towards an Isomorphism Dichotomy for Hereditary Graph Classes
DOI: 10.1007/S00224-017-9775-8
description: scientific article; zbMATH DE number 6833241