Some geometric applications of Dilworth's theorem

DOI10.1007/BF02574361zbMath0799.05018MaRDI QIDQ1330876

János Pach, Jenö Töröcsik

Publication date: 10 August 1994

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

transversalpartially ordered setsgeometric graphplanerectanglesDilworth's theorem

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Planar graphs; geometric and topological aspects of graph theory (05C10) Convex sets in (2) dimensions (including convex curves) (52A10) Ramsey theory (05D10)

Related Items (22)

Jin Akiyama: a friend and his mathematics (on the occasion of his 60th birthday) ⋮ Segment orders ⋮ On the chromatic number of some geometric type Kneser graphs ⋮ Symmetric chain partitions of orthocomplemented posets ⋮ A bipartite analogue of Dilworth's theorem ⋮ Applications of the crossing number ⋮ Turán-type results for partial orders and intersection graphs of convex sets ⋮ Triangle-free intersection graphs of line segments with large chromatic number ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Coloring Hasse diagrams and disjointness graphs of curves ⋮ Note on geometric graphs ⋮ Tangled Thrackles ⋮ On grids in topological graphs ⋮ Disjoint edges in geometric graphs ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Turán-type results for complete \(h\)-partite graphs in comparability and incomparability graphs ⋮ Improved Ramsey-type results for comparability graphs ⋮ On the chromatic number of disjointness graphs of curves ⋮ A bipartite analogue of Dilworth's theorem for multiple partial orders ⋮ An almost optimal bound on the number of intersections of two simple polygons

Cites Work

• Knoten mit zwei Brücken
• Covering and coloring problems for relatives of intervals
• Generalized exponents of a free arrangement of hyperplanes and Shepherd- Todd-Brieskorn formula
• Bounding the vertex cover number of a hypergraph
• Forcing disjoint segments in the plane
• A decomposition theorem for partially ordered sets
• Three-Fold Branched Coverings of S 3
• On Sets of Distances of n Points
• Disjoint edges in geometric graphs
• Knots
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some geometric applications of Dilworth's theorem