Characterization problems for graphs, partially ordered sets, lattices, and families of sets

DOI10.1016/S0012-365X(76)80011-8zbMath0356.06007OpenAlexW2068654529WikidataQ106106673 ScholiaQ106106673MaRDI QIDQ1237785

John I. jun. Moore, William T. jun. Trotter

Publication date: 1977

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(76)80011-8

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (05C99)

Related Items (82)

Circular-arc graphs with clique cover number two ⋮ A characterization of the \(n\)-agent Pareto dominance relation ⋮ 3-interval irreducible partially ordered sets ⋮ Subclasses of circular-arc bigraphs: Helly, normal and proper ⋮ A recognition algorithm for orders of interval dimension two ⋮ On-line algorithms for ordered sets and comparability graphs ⋮ On the problem of how to represent a graph taking into account an additional structure ⋮ Vertex deletion into bipartite permutation graphs ⋮ Dimension of restricted classes of interval orders ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Reconstructibility and perfect graphs ⋮ Properties of Large 2-Crossing-Critical Graphs ⋮ Planar graphs and poset dimension ⋮ On orthogonal ray graphs ⋮ An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs ⋮ Generalizations of semiorders: A review note ⋮ 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs ⋮ A characterization of Robert's inequality for boxicity ⋮ A characterization of two-agent Pareto representable orderings ⋮ Partial Characterizations of Circular-Arc Graphs ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ New characterizations of proper interval bigraphs ⋮ A generalization of Turan's theorem to directed graphs ⋮ Forbidden substructure for interval digraphs/bigraphs ⋮ Unnamed Item ⋮ Block Crossings in Storyline Visualizations ⋮ Large minimal realizers of a partial order. II ⋮ A structure theory for ordered sets ⋮ On orthogonal ray trees ⋮ Finite dimensional scattered posets ⋮ On the dimension of the Cartesian product of relations and orders ⋮ Stacks and splits of partially ordered sets ⋮ Unnamed Item ⋮ Representing preferences using intervals ⋮ Split orders ⋮ A combinatorial problem involving graphs and matrices ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Co-TT graphs and a characterization of split co-TT graphs ⋮ The competition hypergraphs of doubly partial orders ⋮ The interval inclusion number of a partially ordered set ⋮ Permutation statistics and linear extensions of posets ⋮ Two remarks on circular arc graphs ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ Recent results on containment graphs of paths in a tree ⋮ On the dimension of partially ordered sets ⋮ Hypergraphs and intervals ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ The complexity of tropical graph homomorphisms ⋮ Applications of Ramsey theory ⋮ What is reconstruction for ordered sets? ⋮ Vertex deletion into bipartite permutation graphs ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ On a certain numbering of the vertices of a hypergraph ⋮ Maximal dimensional partially ordered sets. III: A characterization of Hiraguchi's inequality for interval dimension ⋮ Representation characterizations of chordal bipartite graphs ⋮ Unnamed Item ⋮ On the complexity of posets ⋮ Interval hypergraphs and D-interval hypergraphs ⋮ On \(k\)-tree containment graphs of paths in a tree ⋮ Dimension and matchings in comparability and incomparability graphs. ⋮ The granular partition lattice of an information table ⋮ Hereditary semiorders and enumeration of semiorders by dimension ⋮ Dimensions of hypergraphs ⋮ Representation theorems for graphs whose vertex set is partially ordered ⋮ Dimension preserving contractions and a finite list of 3-irreducible posets ⋮ Two-dimensional partial orderings: Recursive model theory ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ The Complexity of the Partial Order Dimension Problem ⋮ Dimension of valued relations ⋮ A generalization of the theorem of Lekkerkerker and Boland ⋮ Split semiorders ⋮ Lexicographic Orientation Algorithms ⋮ A type of algebraic structure related to sets of intervals ⋮ On realizable biorders and the biorder dimension of a relation ⋮ Unnamed Item ⋮ Circular representation problem on hypergraphs ⋮ The dimension of the Cartesian product of partial orders ⋮ The complexity of facets (and some facets of complexity) ⋮ Interval dimension is a comparability invariant ⋮ Paretian partial orders: the two-agent case ⋮ Posets with large dimension and relatively few critical pairs ⋮ Partial Characterizations of 1‐Perfectly Orientable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Certain partially ordered sets of dimension three
• Dimension of the crown \(S^k_n\)
• Arbres et dimension des ordres
• Some theorems on graphs and posets
• A generalization of Hiraguchi's: Inequality for posets
• Maximal dimensional partially ordered sets. III: A characterization of Hiraguchi's inequality for interval dimension
• On the complexity of posets
• Intransitive indifference with unequal indifference intervals
• A structure theorem for the consecutive 1's property
• Matrix characterizations of circular-arc graphs
• Maximal dimensional partially ordered sets. I: Hiraguchi's theorem
• Structure theorems for some circular-arc graphs
• Crowns, Fences, and Dismantlable Lattices
• Representation of a finite graph by a set of intervals on the real line
• Faithful Representation of a Family of Sets by a Set of Intervals
• Planar Lattices
• Inequalities in Dimension Theory for Posets
• A forbidden subposet characterization of an order — dimension inequality
• The Dimension of a Comparability Graph
• Transitiv orientierbare Graphen
• Characterizing circular-arc graphs
• Partial orders of dimension 2
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Characterization problems for graphs, partially ordered sets, lattices, and families of sets