Graph Classes and Forbidden Patterns on Three Vertices
From MaRDI portal
Publication:5855535
DOI10.1137/19M1280399zbMath1504.05278arXiv1812.05913MaRDI QIDQ5855535
Laurent Feuilloley, Michel 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
Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Oriented expressions of graph properties ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Describing hereditary properties by forbidden circular orderings
Cites Work
- A new LBFS-based algorithm for cocomparability graph recognition
- Complexity issues for the sandwich homogeneous set problem
- Finding and counting given length cycles
- On rigid circuit graphs
- The strong perfect graph theorem
- An optimal greedy heuristic to color interval graphs
- A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
- Maximum induced matchings for chordal graphs in linear time
- Bipartite permutation graphs
- A unified approach to domination problems on interval graphs
- The book thickness of a graph
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- The splittance of a graph
- Trivially perfect graphs
- Modular decomposition and transitive orientation
- A new graph parameter to measure linearity
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Threshold graphs and related topics
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- Optimal greedy algorithms for indifference graphs
- Incidence matrices and interval graphs
- On a property of the class of n-colorable graphs
- Partitioning cographs into cliques and stable sets
- On the Power of Graph Searching for Cocomparability Graphs
- On some simplicial elimination schemes for chordal graphs
- Ordering without Forbidden Patterns
- Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
- The LBFS Structure and Recognition of Interval Graphs
- Domination on Cocomparability Graphs
- 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
- A Unified View of Graph Searching
- The Complexity of the Partial Order Dimension Problem
- The Comparability Graph of a Tree
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Laying Out Graphs Using Queues
- Comparing Queues and Stacks As Machines for Laying Out Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Graph Classes: A Survey
- Asteroidal Triple-Free Graphs
- Intersection Graphs of Rays and Grounded Segments
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- On the computational complexity of ordered subgraph recognition
- The book crossing number of a graph
- Reducibility among Combinatorial Problems
- Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
- (c-)AND: A new graph model
- Multiplying matrices faster than coppersmith-winograd
- Berge trigraphs
- Transitiv orientierbare Graphen
- Permutation Graphs and Transitive Graphs
- A Dual of Dilworth's Decomposition Theorem
- A Characterization of Comparability Graphs and of Interval Graphs
- Partially Ordered Sets
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Graph Classes and Forbidden Patterns on Three Vertices
