A short proof that `proper = unit'
From MaRDI portal
Publication:1301726
DOI10.1016/S0012-365X(98)00310-0zbMath0932.05065arXivmath/9811036MaRDI QIDQ1301726
Kenneth P. Bogart, Douglas B. West
Publication date: 21 March 2000
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9811036
characterizationinterval orderinterval graphsemiordersproper interval representationsunit interval representations
Combinatorics of partially ordered sets (06A07) Structural characterization of families of graphs (05C75) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Uniform embeddings for Robinson similarity matrices ⋮ Combining overlap and containment for gene assembly in ciliates ⋮ Unnamed Item ⋮ On some subclasses of interval catch digraphs ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Toric rings arising from vertex cover ideals ⋮ Random generation and enumeration of bipartite permutation graphs ⋮ On characterizing proper max-point-tolerance graphs ⋮ A characterization of unit interval bigraphs of open and closed intervals ⋮ Defensive domination in proper interval graphs ⋮ Subgraph isomorphism in graph classes ⋮ Canonical antichains of unit interval and bipartite permutation graphs ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Extended formulations for order polytopes through network flows ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ The Roberts characterization of proper and unit interval graphs ⋮ On the non-unit count of interval graphs ⋮ A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ Unit representation of semiorders. I: Countable sets ⋮ Unit and proper tube orders ⋮ Unit Interval Graphs of Open and Closed Intervals ⋮ Powers of cycles, powers of paths, and distance graphs ⋮ Fractional weak discrepancy and split semiorders ⋮ Improved randomized online scheduling of intervals and jobs ⋮ Some remarks on the geodetic number of a graph ⋮ A matrix characterization of interval and proper interval graphs ⋮ Unnamed Item ⋮ Precoloring extension on unit interval graphs ⋮ Mixed unit interval graphs ⋮ Quasimonotone graphs ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ On rectangle intersection graphs with stab number at most two ⋮ On the maximum cardinality cut problem in proper interval graphs and related graph classes ⋮ Sortable simplicial complexes and \(t\)-independence ideals of proper interval graphs ⋮ Online interval scheduling: Randomized and multiprocessor cases ⋮ On sum coloring and sum multi-coloring for restricted families of graphs ⋮ Short Models for Unit Interval Graphs
Cites Work
