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 u′v′ 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.

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}, }