The chromatic number of ordered graphs with constrained conflict graphs

zbMATH Open1375.05080arXiv1610.01111MaRDI QIDQ4595640FDOQ4595640

Authors: Jonathan Rollin, Torsten Ueckerdt, Maria Axenovich 

Publication date: 6 December 2017

Abstract: An ordered graph $G$ is a graph whose vertex set is a subset of integers. The edges are interpreted as tuples $(u,v)$ with $u<v$. For a positive integer $s$, a matrix $Minmathbb{Z}^{simes4}$, and a vector $mathbfp=(p,ldots,p)inmathbb{Z}^s$ we build a conflict graph by saying that edges $(u,v)$ and $(x,y)$ are conflicting if $M(u,v,x,y{)}^{o}pgeqmathbfp$ or $M(x,y,u,v{)}^{o}pgeqmathbfp$, where the comparison is componentwise. 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_{e}xtcli(M,p,w)$ of ordered graphs $G$ with no $w$ pairwise conflicting edges and the maximum chromatic number $X_{e}xtind(M,p,a)$ of ordered graphs $G$ with no $a$ pairwise non-conflicting edges. We determine $X_{e}xtcli(M,p,w)$ and $X_{e}xtind(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 $mathbbZ$.

Full work available at URL: https://arxiv.org/abs/1610.01111

Recommendations

• Chromatic number of ordered graphs with forbidden ordered subgraphs
• Ordered coloring grids and related graphs
• Ramsey numbers of interval 2-chromatic ordered graphs
• Ramsey numbers of ordered graphs
• Ramsey numbers of ordered graphs

zbMATH Keywords

integer graphsunordered graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cited In (1)

• Ordered coloring grids and related graphs

This page was built for publication: The chromatic number of ordered graphs with constrained conflict graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595640)