The characterization of good ordered graphs by monotone caterpillars
The characterization of good ordered graphs by monotone caterpillars
Let 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 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 -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
Sign in to submit a solution.
No solutions have been posted yet.