The characterization of good ordered graphs by monotone caterpillars

About 4 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.