Independent packings in structured graphs

Representation of a finite graph by a set of intervals on the real line

C. Lekkeikerker, James Boland · Fundamenta Mathematicae · 1962 · 715 citations

Geometric Graph Theory, Graph Theory, Finite Graph +6

A Characterization of Comparability Graphs and of Interval Graphs

Paul C. Gilmore, Alan J. Hoffman · Canadian Journal of Mathematics · 1964 · 600 citations · Full text

Mathematical Programming, Comparability Graphs, Directed Graph +12

Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

Fǎnicǎ Gavril · SIAM Journal on Computing · 1972 · 532 citations

Minimum Coloring, Engineering, Planar Graph +17

The Complexity of Coloring Circular Arcs and Chords

M. R. Garey, David S. Johnson, Gary L. Miller et al. · SIAM Journal on Algebraic and Discrete Methods · 1980 · 390 citations

Geometric Graph Theory, Engineering, Graph Theory +15

Node-Deletion Problems on Bipartite Graphs

Mihalis Yannakakis · SIAM Journal on Computing · 1981 · 296 citations

Engineering, Graph Theory, Extremal Graph Theory +14