On counting interval lengths of interval graphs

DOI10.1016/J.DAM.2010.07.006MaRDI QIDQ531590zbMATH OpenOpenAlexFDO

Authors Márcia R. Cerioli, Fabiano de S. Oliveira, Jayme L. Szwarcfiter

Publication date 19 April 2011

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

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

zbMATH Keywords

interval countinterval graphslengths of intervals

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Recommendations

• On the enumeration of interval graphs
• On the non-unit count of interval graphs
• On the classes of interval graphs of limited nesting and count of lengths
• On the classes of interval graphs of limited nesting and count of lengths
• scientific article; zbMATH DE number 846956
• On the domatic number of interval graphs
• Some results about the interval number of a graph
• Interval count of generalizations of threshold graphs
• On the interval number of special graphs
• A note on the interval number of a graph

Cites work

• A certifying algorithm for the consecutive-ones property
• Algorithmic graph theory and perfect graphs
• Betweenness, orders and interval graphs
• Characterizing intersection graphs of substars of a star.
• scientific article; zbMATH DE number 5963787 (Why is no real title available?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Interval Count of a Graph

Cited in

(16)

• The total interval number of a graph
• On the classes of interval graphs of limited nesting and count of lengths
• Graphs of interval count two with a given partition
• On subclasses of interval count two and on Fishburn's conjecture
• Two problems on interval counting
• Dimension of restricted classes of interval orders
• On the thinness and proper thinness of a graph
• On representing an interval graph using the minimum number of interval lengths
• Unit and single point interval graphs
• On the classes of interval graphs of limited nesting and count of lengths
• On the non-unit count of interval graphs
• Interval count of generalizations of threshold graphs
• Maximum cut on interval graphs of interval count four is NP-complete
• Relation between classes of graphs with interval count k
• Semi-proper interval graphs
• Fast and simple algorithms to count the number of vertex covers in an interval graph

This page was built for publication: On counting interval lengths of interval graphs

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