Ramsey numbers of interval 2-chromatic ordered graphs

DOI10.1007/S00373-019-02057-8zbMATH Open1426.05115arXiv1805.05900OpenAlexW2963118319WikidataQ127585711 ScholiaQ127585711MaRDI QIDQ2334071FDOQ2334071

Authors: Dana Neidinger, Douglas B. West 

Publication date: 6 November 2019

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: An ordered graph $G$ is a graph together with a specified linear ordering on the vertices, and its interval chromatic number is the minimum number of independent sets consisting of consecutive vertices that are needed to partition the vertex set. The $t$-color Ramsey number $R_t(G)$ of an ordered graph $G$ is the minimum number of vertices of an ordered complete graph such that every edge-coloring from a set of $t$ colors contains a monochromatic copy of $G$ such that the copy of $G$ preserves the original ordering on $G$. An ordered graph is $k$-ichromatic if it has interval chromatic number $k$. We obtain lower bounds linear in the number of vertices for the Ramsey numbers of certain classes of 2-ichromatic ordered graphs. We also determine the exact value of the $t$-color Ramsey number for two families of 2-ichromatic ordered graphs, and we prove a linear upper bound for a class of 2-ichromatic ordered graphs.

Full work available at URL: https://arxiv.org/abs/1805.05900

Recommendations

• Ramsey numbers of ordered graphs
• Ramsey numbers of ordered graphs
• Ordered Ramsey numbers
• On ordered Ramsey numbers of bounded-degree graphs
• Edge-ordered Ramsey numbers

zbMATH Keywords

ordered graphRamsey numberinterval chromatic number2-chromatic graphTurán number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Davenport-Schinzel theory of matrices
• Forbidden paths and cycles in ordered graphs and matrices
• Title not available (Why is that?)
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• Ordered Ramsey theory and track representations of graphs
• Maximum size of reverse-free sets of permutations
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems
• Ramsey numbers of ordered graphs
• Ordered Ramsey numbers
• Chromatic number of ordered graphs with forbidden ordered subgraphs
• Minimal ordered Ramsey graphs
• Ordered Ramsey numbers of loose paths and matchings
• On the Turán number of ordered forests

Cited In (4)

• The chromatic number of ordered graphs with constrained conflict graphs
• Minimal ordered Ramsey graphs
• Ordered Ramsey theory and track representations of graphs
• Online Ramsey numbers of ordered paths and cycles

This page was built for publication: Ramsey numbers of interval 2-chromatic ordered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2334071)