Chromatic number of ordered graphs with forbidden ordered subgraphs
From MaRDI portal
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.
An ordered graph is a graph together with a linear ordering of its vertex set. The paper considers the behavior of the chromatic number of ordered graphs with forbidden ordered subgraphs. The authors prove and describe several infinite classes of minimal ordered forests. Known results for forests with at most three edges are summarized.
Recommendations
Cited in
(19)- Ordered colourings
- Describing hereditary properties by forbidden circular orderings
- Ramsey numbers of interval 2-chromatic ordered graphs
- Counting ordered graphs that avoid certain subgraphs
- Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes
- The chromatic number of ordered graphs with constrained conflict graphs
- scientific article; zbMATH DE number 975344 (Why is no real title available?)
- On the Turán number of ordered forests
- Coloring polygon visibility graphs and their generalizations
- On asymptotic packing of convex geometric and ordered graphs
- A characterization of edge-ordered graphs with almost linear extremal functions
- Heroes in oriented complete multipartite graphs
- List-3-coloring ordered graphs with a forbidden induced subgraphs
- On computational aspects of ordered matching problems
- A survey of degree-boundedness
- Colouring polygon visibility graphs and their generalizations
- On computational aspects of cores of ordered graphs
- A polynomial-time approximation algorithm for complete interval minors
- Minimal ordered Ramsey graphs
This page was built for publication: Chromatic number of ordered graphs with forbidden ordered subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1715066)
