2018/05/15 by Dana Neidinger, Douglas B. West
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Chromatic scale #Graph #Interval (graph theory) #Limits and Structures in Graph Theory #Partition (number theory) #Ramsey's theorem #Upper and lower bounds #Vertex (graph theory) #Wheel graph #math.CO
paper · pdf · doi:10.1007/s00373-019-02057-8
published as Graphs and Combinatorics (2019) · 13 pages
arxiv created 2018/05/15 · openalex created_date 2018/06/01 · openalex publication_date 2019/06/28 · arxiv updated 2021/02/18 · openalex updated_date 2026/08/06
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 Rt(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.