Min-orderable digraphs

DOI10.1137/19M1241763MaRDI QIDQ5130576zbMATH OpenOpenAlexFDO

Authors Jing Huang, Arash Rafiey, Pavol Hell, R. M. McConnell

Publication date 28 October 2020

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

Full work available at URL https://doi.org/10.1137/19m1241763

zbMATH Keywords

forbidden submatricesgraph classesinterval graphsordering characterizationthreshold tolerance graph

Mathematics Subject Classification ID

Perfect graphs (05C17) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Recommendations

• Interval-like graphs and digraphs
• scientific article; zbMATH DE number 927077
• Interval digraphs: An analogue of interval graphs
• Monotone proper interval digraphs and Min-Max orderings
• Chronological orderings of interval digraphs

Cites work

• Approximation of minimum cost homomorphisms
• Bi‐arc graphs and the complexity of list homomorphisms
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Classifying the Complexity of Constraints Using Finite Algebras
• Co-TT graphs and a characterization of split co-TT graphs
• Containment Graphs, Posets, and Related Classes of Graphs
• Doubly Lexical Orderings of Matrices
• Efficient graph representations
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Incidence matrices and interval graphs
• Interval bigraphs and circular arc graphs
• Interval digraphs: An analogue of interval graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Interval-like graphs and digraphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear-time recognition of circular-arc graphs
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• Monotone proper interval digraphs and Min-Max orderings
• On recognition of threshold tolerance graphs and their complements
• Ordering without forbidden patterns
• Permuting matrices to avoid forbidden submatrices
• Polynomial graph-colorings
• Representation characterizations of chordal bipartite graphs
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The LBFS structure and recognition of interval graphs
• Threshold tolerance graphs

Cited in

(12)

• A recognition algorithm for adjusted interval digraphs
• scientific article; zbMATH DE number 1145349 (Why is no real title available?)
• Monotone proper interval digraphs and Min-Max orderings
• Interval-like graphs and digraphs
• Minimal Representations of Order Types by Geometric Graphs
• Minimum Degree Orderings
• Strong Chordality of Graphs with Possible Loops
• Comparability digraphs: an analogue of comparability graphs
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• Bi-arc digraphs: recognition algorithm and applications
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• A characterization of uniquely representable two-directional orthogonal ray graphs

This page was built for publication: Min-orderable digraphs

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