|
| | | | |
| | | |
| Stat |
Members: 3664
Articles: 2'599'751
Articles rated: 2609
27 December 2024 |
|
| | | | |
|
Article overview
| |
|
|
Chromatic number of ordered graphs with forbidden ordered subgraphs | | Maria Axenovich
; Jonathan Rollin
; Torsten Ueckerdt
; | | Date: |
1 Mar 2016 | | 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{chi(G) | G in 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) is infinity. However, in contrast to
the unordered graphs, we describe an infinite family of ordered forests H with
infinite 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) is finite to a family of so-called
monotonically alternating trees. For non-crossing H we prove that f(H) is
finite 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. | | Source: | arXiv, 1603.0312 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER