Veröffentlichung

Titel:
Chromatic number of ordered graphs with forbidden ordered subgraphs
AutorInnen:
Maria Axenovich
Jonathan Rollin
Torsten Ueckerdt
Kategorie:
Artikel in Zeitschriften
erschienen in:
Combinatorica, Vol. 38(5), pp 1021–1043, 2018
Abstract:

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 f(H) = sup{x(G) | G∈Forb(H)}, 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 uu′ ≺ vv′. 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.

Download:
arXiv
BibTeX-Eintrag:
@article{, author = {Maria Axenovich and Jonathan Rollin and Torsten Ueckerdt}, title = {Chromatic number of ordered graphs with forbidden ordered subgraphs}, journal = {Combinatorica}, volume = {38}, number={5}, pages={1021--1043}, year = {2018}, }
Christoph Doppelbauer | 12.08.2021