Recognizing simple-triangle graphs by restricted 2-chain subgraph cover

DOI10.1016/j.dam.2019.10.028zbMath1439.05167arXiv1605.07322OpenAlexW2985803252WikidataQ126833580 ScholiaQ126833580MaRDI QIDQ2181225

Asahi Takaoka

Publication date: 18 May 2020

Published in: Discrete Applied Mathematics, WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

recognition algorithmthreshold dimension 2 graphsPI graphschain covergraph sandwich problemsimple-triangle graphsthreshold dimension-2 graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs, A recognition algorithm for simple-triangle graphs, A vertex ordering characterization of simple-triangle graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The recognition of triangle graphs
• On orthogonal ray graphs
• On the forbidden induced subgraph sandwich problem
• The chain graph sandwich problem
• Two remarks on circular arc graphs
• Tolerance graphs
• Triangle, parallelogram, and trapezoid orders
• Circular-arc graphs with clique cover number two
• Alternating orientation and alternating colouration of perfect graphs
• Trapezoid graphs and their coloring
• On the Ferrers dimension of a digraph
• Comparability graphs and intersection graphs
• The dimension of planar posets
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Modular decomposition and transitive orientation
• Efficient graph representations
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Sandwich and probe problems for excluding paths
• On the forbidden induced subgraph probe and sandwich problems
• A vertex ordering characterization of simple-triangle graphs
• Algorithmic graph theory and perfect graphs
• Proper and unit tolerance graphs
• A recognition algorithm for orders of interval dimension two
• Threshold graphs and related topics
• On the structure of trapezoid graphs
• Vertex splitting and the recognition of trapezoid graphs
• Representation characterizations of chordal bipartite graphs
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
• Extending Partial Representations of Function Graphs and Permutation Graphs
• The LBFS Structure and Recognition of Interval Graphs
• The Recognition of Tolerance and Bounded Tolerance Graphs
• Linear-Interval Dimension and PI Orders
• The Complexity of the Partial Order Dimension Problem
• On testing isomorphism of permutation graphs
• Sufficient Conditions for Graphs to Have Threshold Number 2
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Topics in Intersection Graph Theory
• Tolerance graphs, and orders
• Graph Classes: A Survey
• On the Interplay Between Interval Dimension and Dimension
• On the 2-Chain Subgraph Cover and Related Problems
• Graph Sandwich Problems
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• Difference graphs
• Threshold Numbers and Threshold Completions