| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 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.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |