Minimal ordered Ramsey graphs
From MaRDI portal
Abstract: An ordered graph is a graph equipped with a linear ordering of its vertex set. A pair of ordered graphs is Ramsey finite if it has only finitely many minimal ordered Ramsey graphs and Ramsey infinite otherwise. Here an ordered graph F is an ordered Ramsey graph of a pair (H,H') of ordered graphs if for any coloring of the edges of F in colors red and blue there is either a copy of H with all edges colored red or a copy of H' with all edges colored blue. Such an ordered Ramsey graph is minimal if neither of its proper subgraphs is an ordered Ramsey graph of (H,H'). If H=H' then H itself is called Ramsey finite. We show that a connected ordered graph is Ramsey finite if and only if it is a star with center being the first or the last vertex in the linear order. In general we prove that each Ramsey finite (not necessarily connected) ordered graph H has a pseudoforest as a Ramsey graph and therefore is a star forest with strong restrictions on the positions of the centers of the stars. In the asymmetric case we show that (H,H') is Ramsey finite whenever H is a so-called monotone matching. Among several further results we show that there are Ramsey finite pairs of ordered stars and ordered caterpillars of arbitrary size and diameter. This is in contrast to the unordered setting where for any Ramsey finite pair (H,H') of forests either one of H or H' is a matching or both are star forests (with additional constraints). Several of our results give a relation between Ramsey finiteness and the existence of sparse ordered Ramsey graphs. Motivated by these relations we characterize all pairs of ordered graphs that have a forest as an ordered Ramsey graph and all pairs of connected ordered graphs that have a pseudoforest as a Ramsey graph.
Recommendations
- On Ramsey minimal graphs
- On Ramsey minimal graphs
- On Ramsey Minimal Graphs
- The minimum degree of Ramsey-minimal graphs
- On the minimum degree of minimal Ramsey graphs
- scientific article; zbMATH DE number 3735863
- Minimal Ramsey graphs with many vertices of small degree
- Ramsey numbers of ordered graphs
- Ramsey numbers of ordered graphs
- Minimal vertex Ramsey graphs and minimal forbidden subgraphs
Cites work
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3672341 (Why is no real title available?)
- scientific article; zbMATH DE number 21734 (Why is no real title available?)
- scientific article; zbMATH DE number 3520447 (Why is no real title available?)
- scientific article; zbMATH DE number 524135 (Why is no real title available?)
- scientific article; zbMATH DE number 1080356 (Why is no real title available?)
- A short proof of the random Ramsey theorem
- An algorithmic framework for obtaining lower bounds for random Ramsey problems
- Chromatic number of ordered graphs with forbidden ordered subgraphs
- Conditions on Ramsey nonequivalence
- Edge-ordered Ramsey numbers
- Off-diagonal ordered Ramsey numbers of matchings
- On Ramsey minimal graphs
- On globally sparse Ramsey graphs
- On graphs with Ramsey-infinite blocks
- On ordered Ramsey numbers of bounded-degree graphs
- On the minimum degree of minimal Ramsey graphs
- On the use of senders in generalized Ramsey theory for graphs
- Ordered Ramsey numbers
- Ordered Ramsey numbers of loose paths and matchings
- Ramsey \((K_ {1,2},K_ 3)\)-minimal graphs
- Ramsey equivalence of \(K_n\) and \(K_n+K_{n-1}\)
- Ramsey numbers of interval 2-chromatic ordered graphs
- Ramsey numbers of ordered graphs
- Ramsey numbers of sparse hypergraphs
- Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
- Ramsey-minimal graphs for star-forests
- Sharp thresholds for certain Ramsey properties of random graphs
- Symmetric and asymmetric Ramsey properties in random hypergraphs
- The Ramsey number of a graph with bounded maximum degree
- The Ramsey property for graphs with forbidden complete subgraphs
- The structure of critical Ramsey graphs
- Threshold Functions for Ramsey Properties
- Threshold functions for small subgraphs
- Two variants of the size Ramsey number
- Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems
- What is Ramsey-equivalent to a clique?
Cited in
(2)
This page was built for publication: Minimal ordered Ramsey graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q785822)
