Unit and single point interval graphs

DOI10.1016/J.DAM.2012.02.014MaRDI QIDQ427904zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Jayme L. Szwarcfiter

Publication date 18 June 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.02.014

zbMATH Keywords

interval graphsthreshold graphsunit interval graphsinterval count

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Simple linear time recognition of unit interval graphs
• On unit interval graphs with integer endpoints
• Recognition and characterization of unit interval graphs with integer endpoints
• Integral mixed unit interval graphs
• Unit mixed interval graphs

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A linear-time algorithm for proper interval graph recognition
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Betweenness, orders and interval graphs
• Chronological orderings of interval graphs
• On counting interval lengths of interval graphs
• The Interval Count of a Graph
• The LBFS structure and recognition of interval graphs
• The Roberts characterization of proper and unit interval graphs
• Threshold graphs and related topics

Cited in

(7)

• Graphs of interval count two with a given partition
• Two problems on interval counting
• Interval orders with two interval lengths
• On the non-unit count of interval graphs
• Recognition and characterization of unit interval graphs with integer endpoints
• Interval line graphs
• On subclasses of interval count two and on Fishburn's conjecture

This page was built for publication: Unit and single point interval graphs

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