Skip to main content
Presentation
Orders: Interval, Interval-Probe, and Interval-k
41st Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL
  • David E. Brown, Utah State University
Document Type
Presentation
Publication Date
1-1-2010
Abstract

If an interval graph is such that its complement can be oriented transitively, that orientation yields an interval order. A graph G is an interval-probe graph if its vertices can be partitioned into P (probes) and N (nonprobes) and each vertex v can correspond to an interval Iv so that vertices u and v are adjacent if and only if Iu ∩Iv ̸= Ø and {u,v}∩P ̸= Ø. A graph G is an interval k-graph if its vertices can be properly colored and each vertex v can correspond to an interval Iv so that vertices u and v are adjacent if and only if Iu ∩Iv ̸= Ø and u and v are colored differently. Interval probe graphs generalize interval graphs and interval k-graphs generalize interval-probe graphs. This talk will contain recent characterizations of interval- probe orders (order obtained from a transitive orientation of an interval-probe graph) of interval k-orders (order obtained from a transitive orientation of an interval k-graph).

Citation Information
David E. Brown. "Orders: Interval, Interval-Probe, and Interval-k" 41st Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL (2010)
Available at: http://works.bepress.com/david_brown/26/