On-line coloring between two lines

DOI10.4230/LIPICS.SOCG.2015.630MaRDI QIDQ5368717zbMATH OpenOpenAlexFDO

Authors Stefan Felsner, Piotr Micek, Torsten Ueckerdt

Publication date 10 October 2017

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

zbMATH Keywords

cocomparability graphsintersection graphsonline coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics of partially ordered sets (06A07) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Online algorithms; streaming algorithms (68W27)

Abstract: We study on-line colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the representation is a connected set contained in the strip between the lines and touches both. Some of the graph classes admitting such a representation are permutation graphs (segments), interval graphs (axis-aligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an on-line algorithm coloring graphs given by convex sets between two lines that uses $O(omeg{a}^3)$ colors on graphs with maximum clique size $omega$. In contrast intersection graphs of segments attached to a single line may force any on-line coloring algorithm to use an arbitrary number of colors even when $omega=2$. The {em left-of} relation makes the complement of intersection graphs of objects between two lines into a poset. As an aside we discuss the relation of the class $mathcalC$ of posets obtained from convex sets between two lines with some other classes of posets: all $2$-dimensional posets and all posets of height $2$ are in $mathcalC$ but there is a $3$-dimensional poset of height $3$ that does not belong to $mathcalC$. We also show that the on-line coloring problem for curves between two lines is as hard as the on-line chain partition problem for arbitrary posets.

Recommendations

• scientific article; zbMATH DE number 65699
• scientific article; zbMATH DE number 7758354
• On-line edge-coloring with a fixed number of colors
• scientific article; zbMATH DE number 2080195
• scientific article; zbMATH DE number 4134074
• On multi-coloured lines in a linear space
• Approximation and Online Algorithms
• On-line list colouring of graphs

Cited in

(4)

• Online and quasi-online colorings of wedges and intervals
• Open problems on graph coloring for special graph classes
• Online and quasi-online colorings of wedges and intervals
• scientific article; zbMATH DE number 5844107 (Why is no real title available?)

This page was built for publication: On-line coloring between two lines

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