The characterization of good ordered graphs by monotone caterpillars

From papers

Let G<G^< be a connected ordered graph. An ordered graph is good if it has the corresponding ordered Ramsey property used in the paper, and a monotone caterpillar graph is the class characterized in the source by the forbidden ordered subgraphs in Figure 2.

Monotone-caterpillar characterization conjecture. The ordered graph G<G^< is good if and only if it is a monotone caterpillar graph.

The authors found no counterexamples among the small graphs they exhaustively searched and verified that there are no 44-good graphs with at most six vertices other than monotone caterpillar graphs. A proof of the characterization remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Martin Balko and Marian Poljak, “On off-diagonal ordered Ramsey numbers of nested matchings”, arXiv:2201.07637 (2022).

Solutions 0

No solutions have been posted yet.