Chromatic Number of Ordered Graphs with Forbidden Ordered Subgraphs

摘要

It is well-known that the graphs not containing a given graph H as a subgraph have bounded chromatic number if and only if H is acyclic. Here we consider ordered graphs, i.e., graphs with a linear ordering ? on their vertex set, and the function where Forb(?)(H) denotes the set of all ordered graphs that do not contain a copy of H.If H contains a cycle, then as in the case of unordered graphs, f(?)(H)=. However, in contrast to the unordered graphs, we describe an infinite family of ordered forests H with f(?)(H) =. An ordered graph is crossing if there are two edges uv and uv with u ? u ? v ? v. For connected crossing ordered graphs H we reduce the problem of determining whether f(?)(H) to a family of so-called monotonically alternating trees. For non-crossing H we prove that f(?)(H) if and only if H is acyclic and does not contain a copy of any of the five special ordered forests on four or five vertices, which we call bonnets. For such forests H, we show that f(?)(H)2(|V(H)|) and that f(?)(H)2|V (H)|-3 if H is connected.