Veröffentlichung

Titel:
The chromatic number of ordered graphs with constrained conflict graphs
AutorInnen:
Maria Axenovich
Jonathan Rollin
Torsten Ueckerdt
Kategorie:
Artikel in Zeitschriften
erschienen in:
Australasian Journal of Combinatorics, Vol. 69, pp. 74–104, 2017
Abstract:

An ordered graph G is a graph whose vertices are the first n positive integers. The edges are interpreted as tuples (u, v) with u < v. For a positive integer s, a matrix M ∈ Zs×4 , and a vector p = (p, . . . , p) ∈ Zs we build a conflict graph whose vertices are the edges of G by saying that edges (u, v) and (x, y) are conflicting if M(u, v, x, y)T >= p or M(x, y, u, v)T >= p,
where the comparison is component-wise. This new framework generalizes many natural concepts of ordered and unordered graphs, such as the page-number, queue-number, band-width, interval chromatic number, and forbidden ordered matchings.


For fixed M and p, we investigate how the chromatic number of G depends on the structure of its conflict graph. Specifically, we study the maximum chromatic number Xcli(M, p, w) of ordered graphs G with no w pairwise conflicting edges and the maximum chromatic number Xind(M, p, a) of ordered graphs G with no a pairwise non-conflicting edges. We determine Xcli(M, p, w) and Xind(M, p, a) exactly whenever M consists of one row with entries in {−1, 0, +1} and moreover consider several cases in which M consists of two rows or has arbitrary entries from Z. As a tool we develop a theory of so-called integer graphs, that is, graphs whose vertex set is an unrestricted subset of the integers.

Download:
Journal Website
BibTeX-Eintrag:
@article{, author = {Maria Axenovich and Jonathan Rollin and Torsten Ueckerdt}, title = {The chromatic number of ordered graphs with constrained conflict graphs}, journal = {Australasian J. Combinatorics}, volume = {69}, pages = {74--104}, year = {2017}, }
Christoph Doppelbauer | 10.05.2024