A Characterization of Comparability Graphs and of Interval Graphs

DOI10.4153/CJM-1964-055-5zbMath0121.26003OpenAlexW2063410295WikidataQ29037122 ScholiaQ29037122MaRDI QIDQ5732670

Publication date: 1964

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4153/cjm-1964-055-5

zbMATH Keywords

combinatorics

Related Items (only showing first 100 items - show all)

Maximum Semiorders in Interval Orders ⋮ Disconnected matchings ⋮ Wurzelbäume und Kantenorientierungen in Graphen ⋮ Extremal Values of the Interval Number of a Graph ⋮ Permutation graphs and the weak Bruhat order ⋮ The frame dimension and the complete overlap dimension of a graph ⋮ On the homogeneous representation of interval graphs ⋮ Flots et tensions dans un graphe ⋮ Testing superperfection of k-trees ⋮ Heterogeneous Multi-resource Allocation with Subset Demand Requests ⋮ Covering the edges with consecutive sets ⋮ Characterizing circular-arc graphs ⋮ Balanced Cohen-Macaulay Complexes ⋮ Complexity of Finding Embeddings in a k-Tree ⋮ Incidence matrices with the consecutive 1’s property ⋮ Temporal interval cliques and independent sets ⋮ A Model for Birdwatching and other Chronological Sampling Activities ⋮ MaxCut on permutation graphs is NP‐complete ⋮ The overfull conjecture on split-comparability and split-interval graphs ⋮ Corrigendum to: ``Complexity and approximability of the happy set problem ⋮ Computing the weighted neighbor isolated tenacity of interval graphs in polynomial time ⋮ Interval graphs with side (and size) constraints ⋮ On chromatic number and perfectness of fuzzy graph ⋮ Partial and simultaneous transitive orientations via modular decompositions ⋮ Partial orders of dimension 2 ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Tree-width and path-width of comparability graphs of interval orders ⋮ Characterizations of graphs having orientations satisfying local degree restrictions ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Algorithms for a maximum clique and a maximum independent set of a circle graph ⋮ Counting Interval Graphs ⋮ Algorithms on circular-arc graphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ Threshold tolerance graphs ⋮ Underlying properties of oriented graphs ⋮ On the tree representation of chordal graphs ⋮ Dual parameterization of Weighted Coloring ⋮ Interval digraphs: An analogue of interval graphs ⋮ Total domination in interval graphs ⋮ Hypergraphs and intervals ⋮ Zur Vorgabe gerichteter Kanten von Vergleichbarkeitsgraphen ⋮ An approximation result for a periodic allocation problem ⋮ Dimension transitiv orientierbarer graphen ⋮ Biclique graphs and biclique matrices ⋮ Domination and Cut Problems on Chordal Graphs with Bounded Leafage ⋮ Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications ⋮ Unnamed Item ⋮ Expansions of Chromatic Polynomials and Log-Concavity ⋮ Graph theory ⋮ Extremal interval graphs ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Unnamed Item ⋮ Disconnected matchings ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Circular permutation graphs ⋮ Efficient Local Representations of Graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ To reorient is easier than to orient: An on-line algorithm for reorientation of graphs ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs ⋮ The Dimension of a Comparability Graph ⋮ Transitiv orientierbare Graphen ⋮ Preference Structures and Co-comparability Graphs ⋮ Orientations of circle graphs ⋮ A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs ⋮ Intersection graphs of paths in a tree ⋮ An optimal algorithm to recognize Robinsonian dissimilarities ⋮ Schedule-induced posets ⋮ Orienting graphs to optimize reachability ⋮ The recognition of geodetically connected graphs ⋮ Finding the minimum bandwidth of an interval graph ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ Bipartite permutation graphs ⋮ Combining overlap and containment for gene assembly in ciliates ⋮ Strictly interval graphs: characterization and linear time recognition ⋮ Fuzzy intersection graphs ⋮ On lexicographic semi-commutations ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ Random interval graphs ⋮ Total domination in interval graphs revisited ⋮ Is there a diagram invariant? ⋮ Simplicial decompositions of graphs: A survey of applications ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs ⋮ On dimensional properties of graphs ⋮ String graphs. I: The number of critical nonstring graphs is infinite ⋮ $P_ 4$-comparability graphs ⋮ Tree loop graphs ⋮ Recognizing graphs without asteroidal triples ⋮ On orientations and shortest paths ⋮ Adjacency matrices of probe interval graphs ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ An $\mathcal O(n^2)$-time algorithm for the minimal interval completion problem ⋮ Recognition and characterization of chronological interval digraphs ⋮ On maximal independent sets of vertices in claw-free graphs ⋮ Extremal values of the interval number of a graph. II ⋮ An algorithm for generating all maximal independent subsets of posets ⋮ Extremal values of the interval number of a graph, II ⋮ A structure theory for ordered sets ⋮ Complement reducible graphs ⋮ On minimal augmentation of a graph to obtain an interval graph

This page was built for publication: A Characterization of Comparability Graphs and of Interval Graphs