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

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, 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, Further hardness results on rainbow and strong rainbow connectivity, An evolution of interval graphs, Computing feasible toolpaths for 5-axis machines, On the complexity of recognizing perfectly orderable graphs, The structure and metric dimension of the power graph of a finite group, An optimal greedy heuristic to color interval graphs, Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem, Comparability graphs and intersection graphs, Representations of graphs and networks (coding, layouts and embeddings), A condition for a family of triangles to be orientable to a cyclic order, Representing graphs via pattern avoiding words, On the non-unit count of interval graphs, A linear-time algorithm for proper interval graph recognition, Characterization and complexity of uniformly nonprimitive labeled 2-structures, Complexity of rainbow vertex connectivity problems for restricted graph classes, Norbert Wiener on the theory of measurement (1914, 1915, 1921), Generalized transitive tournaments and doubly stochastic matrices, Constructing a stochastic critical path network given the slacks: Representation, Strict chordal and strict split digraphs, Structure of concurrency, Counting endpoint sequences for interval orders and interval graphs, On the SPANNING $k$-TREE problem, Line-distortion, bandwidth and path-length of a graph, Sources in posets and comparability graphs, Interval competition graphs of symmetric digraphs, Extending partial representations of proper and unit interval graphs, Thresholds for classes of intersection graphs, Separator orders in interval, cocomparability, and AT-free graphs, Rooted directed path graphs are leaf powers, On sources in comparability graphs, with applications, Dimension-2 poset competition numbers and dimension-2 poset double competition numbers, Paths in interval graphs and circular arc graphs, An algorithm for testing chordality of graphs, A recognition algorithm for the intersection graphs of directed paths in directed trees, Acyclic orientations of a graph and the chromatic and independence numbers, Comparability graphs and a new matroid, Information storage and retrieval - mathematical foundations. II: Combinatorial problems, Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Convex geometry and group choice, Computing the boxicity of a graph by covering its complement by cointerval graphs, Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs, The complexity of comparability graph recognition and coloring, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, Recognizing edge clique graphs among interval graphs and probe interval graphs, On a class of posets and the corresponding comparability graphs, Minimal interval completion through graph exploration, The circular dimension of a graph, The neighbour-scattering number can be computed in polynomial time for interval graphs, A linear time recognition algorithm for proper interval graphs, Dimensions of hypergraphs, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Dual parameterization of weighted coloring, Some remarks on interval graphs, Synthesizing partial orders given comparability information: Partitive sets and slack in critical path networks, Almost all comparability graphs are UPO, Chronological orderings of interval graphs, On realizable biorders and the biorder dimension of a relation, Split graphs of Dilworth number 2, The relationship between the threshold dimension of split graphs and various dimensional parameters, Finding Hamiltonian circuits in interval graphs, Comparability graphs with constraint, partial semi-orders and interval orders, Interval graphs and maps of DNA, Some sequences associated with combinatorial structures, The structure of obstructions to treewidth and pathwidth, Periodic assignment and graph colouring, Compatibility between interval structures and partial orderings, Optimal greedy algorithms for indifference graphs, Rank inequalities for chordal graphs, A faster algorithm to recognize undirected path graphs, Treewidth of cocomparability graphs and a new order-theoretic parameter, Strengthened 0-1 linear formulation for the daily satellite mission planning, Reconfiguration of colorable sets in classes of perfect graphs, $(0,{1\over 2},1)$ matrices which are extreme points of the generalized transitive tournament polytope, Finding minimum height elimination trees for interval graphs in polynomial time, Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs,, Claw-free graphs---a survey, Simultaneous dominance representation of multiple posets, Double-threshold permutation graphs, Restrictions of minimum spanner problems, Unnamed Item, Characterizations of fuzzy interval graphs, Hamiltonian paths, unit-interval complexes, and determinantal facet ideals, A simple linear-time algorithm for computing the center of an interval graph, On double and multiple interval graphs, *-graphs of vertices of the generalized transitive tournament polytope, Characterization of interval graphs that are unpaired 2-disjoint path coverable, Homothetic polygons and beyond: maximal cliques in intersection graphs, Complexity and approximability of the happy set problem, Generalizations of semiorders: A review note, Contact Representations of Planar Graphs: Extending a Partial Representation is Hard, Biclique graph of bipartite permutation graphs, Signed edge domination number of interval graphs, Chronological rectangle digraphs which are two-terminal series-parallel, Biclique graphs of interval bigraphs, Satisfiability problems on intervals and unit intervals, Matching and multidimensional matching in chordal and strongly chordal graphs, Disjoint path covers joining prescribed source and sink sets in interval graphs, MPQ-trees for the orthogonal packing problem, Necessary and possible indifferences, A polynomial algorithm for weighted scattering number in interval graphs, Efficient minus and signed domination in graphs, Cleaning interval graphs, Mixed Search Number of Permutation Graphs, The mutual exclusion scheduling problem for permutation and comparability graphs., A Characterisation of the Minimal Triangulations of Permutation Graphs, Mixed Search Number and Linear-Width of Interval and Split Graphs, Graphs Orientable as Distributive Lattices, The conditional covering problem on unweighted interval graphs with nonuniform coverage radius, A characterization of $P_{4}$-comparability graphs, Classes of perfect graphs, Integral mixed unit interval graphs, Normal Helly circular-arc graphs and its subclasses, A new graph parameter to measure linearity, Reconfiguration of cliques in a graph, Fully dynamic representations of interval graphs, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, A sequential algorithm for finding a maximum weightK-independent set on interval graphs, Which distance-hereditary graphs are cover-incomparability graphs?, Induced matchings in intersection graphs., Graph isomorphism and identification matrices: Sequential algorithms, Burning Two Worlds, New results on induced matchings, Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs, OptimalI-Intersection assignments for graphs: A linear programming approach, I-Colorings,I-Phasings, andI-Intersection assignments for graphs, and their applications, A note on chordal bound graphs and posets, Shiftable intervals, Tree decomposition and discrete optimization problems: a survey, Towards a comprehensive theory of conflict-tolerance graphs, Competition-reachability of a graph, On the interval completion of chordal graphs, On the minimum clique partitioning problem on weighted chordal graphs, Mixed search number and linear-width of interval and split graphs, A Lex-BFS-based recognition algorithm for Robinsonian matrices, The seriation problem and the travelling salesman problem, A recognition algorithm for the intersection graphs of paths in trees, Compact Spaces and Spaces of Maximal Complete Subgraphs, Graphs and partial orderings, Intransitive indifference with unequal indifference intervals, Optimal circular arc representations: Properties, recognition, and construction, On nontransitive indifference, On the complexity of the k-chain subgraph cover problem, On forcibly hereditary P-graphical sequences, Partially ordered sets and their comparability graphs, Betweenness, orders and interval graphs, Concordance graphs, Adjusted Interval Digraphs, Maximal dimensional partially ordered sets. II: Characterization of 2n- element posets with dimension n, A characterization of bivariegated trees, Computing the weighted isolated scattering number of interval graphs in polynomial time, The Interval Count of a Graph, The intersection graphs of subtrees in trees are exactly the chordal graphs, On the canonical ideal of the Ehrhart ring of the chain polytope of a poset, Lexicographic Orientation Algorithms, Characterization of $\mathrm{B}_0$-VPG cocomparability graphs and a 2D visualization of their posets, A census of infinite distance-transitive graphs, Cubicity of Interval Graphs and the Claw Number, Mathematical properties on the hyperbolicity of interval graphs, Clique partitioning with value-monotone submodular cost, Matrix sandwich problems, On the pathwidth of chordal graphs, Independent packings in structured graphs, Recognition algorithm for intersection graphs of edge disjoint paths in a tree