Towards an Isomorphism Dichotomy for Hereditary Graph Classes

DOI10.4230/LIPICS.STACS.2015.689MaRDI QIDQ2955034zbMATH OpenOpenAlexFDO

Authors P. Schweitzer

Publication date 24 January 2017

Full work available at URL https://arxiv.org/abs/1411.1977

zbMATH Keywords

bounded color valenceforbidden induced subgraphsgraph isomorphismmodular decompositionreductions

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25)

Abstract: In this paper we resolve the complexity of the isomorphism problem on all but finitely many of the graph classes characterized by two forbidden induced subgraphs. To this end we develop new techniques applicable for the structural and algorithmic analysis of graphs. First, we develop a methodology to show isomorphism completeness of the isomorphism problem on graph classes by providing a general framework unifying various reduction techniques. Second, we generalize the concept of the modular decomposition to colored graphs, allowing for non-standard decompositions. We show that, given a suitable decomposition functor, the graph isomorphism problem reduces to checking isomorphism of colored prime graphs. Third, we extend the techniques of bounded color valence and hypergraph isomorphism on hypergraphs of bounded color size as follows. We say a colored graph has generalized color valence at most k if, after removing all vertices in color classes of size at most k, for each color class C every vertex has at most k neighbors in C or at most k non-neighbors in C. We show that isomorphism of graphs of bounded generalized color valence can be solved in polynomial time.

Recommendations

• Towards an isomorphism dichotomy for hereditary graph classes
• On the structure of hereditary classes of graphs
• Hereditary classes of graphs: a parametric approach
• On hereditary Helly classes of graphs
• On the size of hereditary classes of graphs
• scientific article; zbMATH DE number 468640
• On axiomatizability of hereditary classes of graphs and matroids
• scientific article; zbMATH DE number 3815
• Critical hereditary graph classes: a survey
• Hadwiger's conjecture for some hereditary classes of graphs: a survey

Cited in

(12)

• Towards an isomorphism dichotomy for hereditary graph classes
• Hereditary classes of graphs: a parametric approach
• Hereditary isomorphy and \(\{-4\}\)-hypomorphy for tournaments
• Graph isomorphism for \((H_1,H_2)\)-free graphs: an almost complete dichotomy
• Bounding clique-width via perfect graphs
• On axiomatizability of hereditary classes of graphs and matroids
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Critical hereditary graph classes: a survey
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Bounding the clique-width of \(H\)-free split graphs
• Graph isomorphism restricted by lists
• Bounding the clique-width of \(H\)-free split graphs

This page was built for publication: Towards an Isomorphism Dichotomy for Hereditary Graph Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955034)