Graph classes and forbidden patterns on three vertices

DOI10.1137/19M1280399MaRDI QIDQ5855535zbMATH OpenFDO

Authors Laurent Feuilloley, M. A. Habib

Publication date 18 March 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsgraph classesvertex orderings with forbidden patterns

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Abstract: This paper deals with graph classes characterization and recognition. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately this strategy usually does not lead to an efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques based on some interesting orderings of the nodes, such as the ones given by traversals. We study specifically graph classes that have an ordering avoiding some ordered structures. More precisely, we consider what we call patterns on three nodes, and the recognition complexity of the associated classes. In this domain, there are two key previous works. Damashke started the study of the classes defined by forbidden patterns, a set that contains interval, chordal and bipartite graphs among others. On the algorithmic side, Hell, Mohar and Rafiey proved that any class defined by a set of forbidden patterns can be recognized in polynomial time. We improve on these two works, by characterizing systematically all the classes defined sets of forbidden patterns (on three nodes), and proving that among the 23 different classes (up to complementation) that we find, 21 can actually be recognized in linear time. Beyond this result, we consider that this type of characterization is very useful, leads to a rich structure of classes, and generates a lot of open questions worth investigating.

Recommendations

• Ordering without forbidden patterns
• Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes
• scientific article; zbMATH DE number 4144022
• scientific article; zbMATH DE number 15355
• The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions

Cites work

• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• A Dual of Dilworth's Decomposition Theorem
• A Unified View of Graph Searching
• A four-sweep LBFS recognition algorithm for interval graphs
• A new LBFS-based algorithm for cocomparability graph recognition
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
• A unified approach to domination problems on interval graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An optimal greedy heuristic to color interval graphs
• Asteroidal Triple-Free Graphs
• Berge trigraphs
• Bipartite permutation graphs
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Complexity issues for the sandwich homogeneous set problem
• Domination on Cocomparability Graphs
• Finding and counting given length cycles
• Graph Classes: A Survey
• Incidence matrices and interval graphs
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Intersection graphs of rays and grounded segments
• Laying Out Graphs Using Queues
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Maximum induced matching algorithms via vertex ordering characterizations
• Maximum induced matchings for chordal graphs in linear time
• Modular decomposition and transitive orientation
• Multiplying matrices faster than coppersmith-winograd
• On a property of the class of n-colorable graphs
• On rigid circuit graphs
• On some simplicial elimination schemes for chordal graphs
• On the computational complexity of ordered subgraph recognition
• On the power of graph searching for cocomparability graphs
• Optimal greedy algorithms for indifference graphs
• Ordering without forbidden patterns
• Partially Ordered Sets
• Partitioning cographs into cliques and stable sets
• Permutation Graphs and Transitive Graphs
• Reducibility among combinatorial problems
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Stacks, queues and tracks: layouts of graph subdivisions
• Subcubic equivalences between path, matrix, and triangle problems
• Survey of distributed decision
• The Comparability Graph of a Tree
• The Complexity of the Partial Order Dimension Problem
• The LBFS structure and recognition of interval graphs
• The book crossing number of a graph
• The book thickness of a graph
• The splittance of a graph
• The strong perfect graph theorem
• Threshold graphs and related topics
• Transitiv orientierbare Graphen
• Trivially perfect graphs
• Vertex ordering characterizations of graphs of bounded asteroidal number
• p-box: a new graph model

Cited in

(10)

• Orientations without forbidden patterns on three vertices
• Graph classes equivalent to 12-representable graphs
• Forbidden patterns in temporal graphs resulting from encounters in a corridor
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Oriented expressions of graph properties
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• Three forbidden subgraphs for line graphs
• Ordering without forbidden patterns
• Tree-layout based graph classes: proper chordal graphs
• Describing hereditary properties by forbidden circular orderings

This page was built for publication: Graph classes and forbidden patterns on three vertices

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