End vertices in interval graphs

DOI10.1016/0166-218X(88)90071-6MaRDI QIDQ1119662zbMATH OpenOpenAlexFDO

Authors John Gimbel

Publication date 1988

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

Full work available at URL https://doi.org/10.1016/0166-218x(88)90071-6

zbMATH Keywords

end verticesinterval graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

Review text

An interval graph is a graph in which there is a one-to-one correspondence between vertices and a family of intervals on the line such that two vertices are adjacent if and only if the corresponding intervals overlap. An end vertex in an interval graph corresponds to the leftmost or rightmost interval in some modeling family of intervals. This note presents a simple forbidden-subgraph characterization of end vertices in an interval graph.

Recommendations

• scientific article; zbMATH DE number 4095511
• End simplicial vertices in path graphs
• Chronological orderings of interval graphs
• Homogeneously representable interval graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs

Cites work

• Homogeneously representable interval graphs
• Representation of a finite graph by a set of intervals on the real line

Cited in

(9)

• Homogeneously representable interval graphs
• Representations of graphs and networks (coding, layouts and embeddings)
• On sources in comparability graphs, with applications
• Toll convexity
• End simplicial vertices in path graphs
• End vertices in containment interval graphs
• Weakly toll convexity and proper interval graphs
• Sources in posets and comparability graphs
• Graphs with span 1 and shortest optimal walks

This page was built for publication: End vertices in interval graphs

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