Characterizing circular-arc graphs

DOI10.1090/S0002-9904-1970-12628-3zbMath0204.24401OpenAlexW2125999673MaRDI QIDQ5602682

Alan C. Tucker

Publication date: 1970

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0002-9904-1970-12628-3

Related Items

Extremal Values of the Interval Number of a Graph, Graphs of edge-intersecting and non-splitting paths, Hamiltonian circuits in interval graph generalizations, Algorithmic aspects of intersection graphs and representation hypergraphs, Intersection graphs of Helly families of subtrees, Short proofs for interval digraphs, On dimensional properties of graphs, Linear-time recognition of Helly circular-arc models and graphs, On linear and circular structure of (claw, net)-free graphs, Algorithms and complexity of sandwich problems in graphs (extended abstract), On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid, Structural results on circular-arc graphs and circle graphs: a survey and the main open problems, On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid, A linear-time algorithm for clique-coloring problem in circular-arc graphs, Obstacle numbers of graphs, Representation characterizations of chordal bipartite graphs, Algorithms for clique-independent sets on subclasses of circular-arc graphs, Finding cut-vertices in the square roots of a graph, Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Graph theory, Canonical representations for circular-arc graphs using flip sets, Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Lexicographic Orientation Algorithms, Describing hereditary properties by forbidden circular orderings, Partial Characterizations of 1‐Perfectly Orientable Graphs, Graphs and digraphs represented by intervals and circular arcs

Cites Work

• Unnamed Item
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Representation of a finite graph by a set of intervals on the real line
• A Characterization of Comparability Graphs and of Interval Graphs