Comparability graphs and a new matroid

DOI10.1016/0095-8956(77)90049-1zbMath0352.05023OpenAlexW2008587336MaRDI QIDQ1235707

Martin Charles Golumbic

Publication date: 1977

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(77)90049-1

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99)

Related Items

The homogeneous set sandwich problem ⋮ On finding the jump number of a partial order by substitution decomposition ⋮ An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Recognizing interval digraphs and interval bigraphs in polynomial time ⋮ Containment graphs and posets of paths in a tree: wheels and partial wheels ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ On the X-join decomposition for undirected graphs ⋮ An algorithm for generating all maximal independent subsets of posets ⋮ Partitive hypergraphs ⋮ Partitioned probe comparability graphs ⋮ New results on induced matchings ⋮ An algorithm for finding homogeneous pairs ⋮ Constructing a stochastic critical path network given the slacks: Representation ⋮ \(P_ 4\)-trees and substitution decomposition ⋮ New algorithms and complexity status of the reducibility problem of sequences in open shop scheduling minimizing the makespan ⋮ On incomplete preference structures ⋮ The complexity of comparability graph recognition and coloring ⋮ A note on perfect Gaussian elimination ⋮ Synthesizing partial orders given comparability information: Partitive sets and slack in critical path networks ⋮ Chronological orderings of interval graphs ⋮ On realizable biorders and the biorder dimension of a relation ⋮ Comparability graphs with constraint, partial semi-orders and interval orders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of comparability graph recognition and coloring
• Graphs and partial orderings
• Partially ordered sets and their comparability graphs
• Triangulated graphs and the elimination process
• Enumeration of vacuously transitive relations
• Representation of a finite graph by a set of intervals on the real line
• An Introduction to Matroid Theory
• Segment-Preserving Maps of Partial Orders
• A Note on "The Comparability Graph of a Tree"
• Transitiv orientierbare Graphen
• Flots et tensions dans un graphe
• An interval graph is not a comparability graph
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Uniquely Partially Orderable Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Permutation Graphs and Transitive Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Partially Ordered Sets