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 ∈ Z^s×4 , and a vector p = (p, . . . , p) ∈ Z^s 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 X_cli(M, p, w) of ordered graphs G with no w pairwise conflicting edges and the maximum chromatic number X_ind(M, p, a) of ordered graphs G with no a pairwise non-conflicting edges. We determine X_cli(M, p, w) and X_ind(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}, }