A Characterization of Comparability Graphs and of Interval Graphs

Cited in

(only showing first 100 items - show all)

Permutation graphs and the weak Bruhat order
Counting Interval Graphs
An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
Integral mixed unit interval graphs
Normal Helly circular-arc graphs and its subclasses
Biclique graphs of interval bigraphs
Some sequences associated with combinatorial structures
Isolated scattering number can be computed in polynomial time for interval graphs
The Dimension of a Comparability Graph
Partial and simultaneous transitive orientations via modular decompositions
A Characterisation of the Minimal Triangulations of Permutation Graphs
A characterization of \(P_{4}\)-comparability graphs
Incidence matrices with the consecutive 1’s property
Counting endpoint sequences for interval orders and interval graphs
Sources in posets and comparability graphs
Interval competition graphs of symmetric digraphs
The circular dimension of a graph
Characterizations of fuzzy interval graphs
Graphs Orientable as Distributive Lattices
Separator orders in interval, cocomparability, and AT-free graphs
An optimal algorithm to recognize Robinsonian dissimilarities
Orienting graphs to optimize reachability
A sequential algorithm for finding a maximum weightK-independent set on interval graphs
Biclique graph of bipartite permutation graphs
Satisfiability problems on intervals and unit intervals
Computing the weighted isolated scattering number of interval graphs in polynomial time
String graphs. I: The number of critical nonstring graphs is infinite
The seriation problem and the travelling salesman problem
Efficient minus and signed domination in graphs
Flots et tensions dans un graphe
Tree decomposition and discrete optimization problems: a survey
Towards a comprehensive theory of conflict-tolerance graphs
Domination and cut problems on chordal graphs with bounded leafage
Bivariate scoring rules: unifying the characterizations of positional scoring rules and Kemeny's rule
Strengthened 0-1 linear formulation for the daily satellite mission planning
Connected proper interval graphs and the guard problem in spiral polygons (extended abstract)
Threshold graphs and synchronization protocols
Recognizing edge clique graphs among interval graphs and probe interval graphs
Lexicographic orientation algorithms
Fuzzy intersection graphs
On the canonical ideal of the Ehrhart ring of the chain polytope of a poset
Mathematical properties on the hyperbolicity of interval graphs
Chronological orderings of interval graphs
Minimal interval completion through graph exploration
Computing the boxicity of a graph by covering its complement by cointerval graphs
\(P_ 4\)-comparability graphs
Extremal values of the interval number of a graph. II
Interval graphs and maps of DNA
On the complexity of the black-and-white coloring problem on some classes of perfect graphs
Independent packings in structured graphs
On minimal augmentation of a graph to obtain an interval graph
Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
Clique partitioning with value-monotone submodular cost
OptimalI-Intersection assignments for graphs: A linear programming approach
Some progress on the Aharoni-Korman conjecture
The frame dimension and the complete overlap dimension of a graph
Optimal circular arc representations: Properties, recognition, and construction
Parameterized dominating set problem in chordal graphs: Complexity and lower bound
To reorient is easier than to orient: An on-line algorithm for reorientation of graphs
A census of infinite distance-transitive graphs
Further hardness results on rainbow and strong rainbow connectivity
Transitiv orientierbare Graphen
Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
Matrix sandwich problems
On double and multiple interval graphs
Intersection graphs of paths in a tree
A linear time recognition algorithm for proper interval graphs
On the complexity of the k-chain subgraph cover problem
On orientations and shortest paths
Graph classes and forbidden patterns on three vertices
Complement reducible graphs
A Model for Birdwatching and other Chronological Sampling Activities
Comparability graphs and intersection graphs
Generalizations of semiorders: A review note
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Combining overlap and containment for gene assembly in ciliates
Graph isomorphism and identification matrices: Sequential algorithms
Contact representations of planar graphs: extending a partial representation is hard
A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
Graphs and partial orderings
Temporal interval cliques and independent sets
On the SPANNING k-TREE problem
Periodic assignment and graph colouring
Claw-free graphs---a survey
Partial orders of dimension 2
Computing the weighted neighbor isolated tenacity of interval graphs in polynomial time
Some remarks on interval graphs
Underlying properties of oriented graphs
The recognition of geodetically connected graphs
Burning two worlds
Gallai-like characterization of strong cocomparability graphs
Synthesizing partial orders given comparability information: Partitive sets and slack in critical path networks
Characterizations of graphs having orientations satisfying local degree restrictions
Convex geometry and group choice
Zur Vorgabe gerichteter Kanten von Vergleichbarkeitsgraphen
MaxCut on permutation graphs is NP‐complete
The overfull conjecture on split-comparability and split-interval graphs
Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
Characterizing circular-arc graphs

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

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