Online Coloring of Comparability Graphs: some results
Marc Demange, Benjamin Leroy‐Beaulieu · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2007
We study online partitioning of posets from a graph theoretical point of view, which is coloring and cocoloring in comparability graphs. For the coloring problem, we analyse the First-Fit algorithm and show a ratio of $O(\\sqrt{n})$; furthermore, we devise an algorithm with a competitivity ratio of $\\frac{\\chi+1}{2}$. For the cocoloring problem, we point out a tight bound of $\\frac{n}{4} + \\frac{1}{2}$ and we give better bounds in some more restricted cocoloring problems.