Document Open Access Logo

On-line Coloring between Two Lines

Authors Stefan Felsner, Piotr Micek, Torsten Ueckerdt

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.630.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Author Details

Stefan Felsner
Piotr Micek
Torsten Ueckerdt

Cite AsGet BibTex

Stefan Felsner, Piotr Micek, and Torsten Ueckerdt. On-line Coloring between Two Lines. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 630-641, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.630

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(w^3) colors on graphs with maximum clique size w. 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 w=2. The 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 C 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 C but there is a 3-dimensional poset of height 3 that does not belong to C. 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.
Keywords
  • intersection graphs
  • cocomparability graphs
  • on-line coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Bartłomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, Grzegorz Matecki, and Piotr Micek. On-line chain partitions of orders: a survey. Order, 29(1):49-73, 2012. Google Scholar
  2. Bartłomiej Bosek, Henry A. Kierstead, Tomasz Krawczyk, Grzegorz Matecki, and Matthew E Smith. An improved subexponential bound for on-line chain partitioning. arXiv preprint arXiv:1410.3247, 2014. Google Scholar
  3. Bartłomiej Bosek and Tomasz Krawczyk. The sub-exponential upper bound for on-line chain partitioning. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science FOCS 2010, pages 347-354. IEEE Computer Soc., Los Alamitos, CA, 2010. Google Scholar
  4. Bartlomiej Bosek, Tomasz Krawczyk, and Edward Szczypka. First-Fit algorithm for the on-line chain partitioning problem. SIAM J. Discrete Math., 23(4):1992-1999, 2010. Google Scholar
  5. Derek G. Corneil and P. A. Kamula. Extensions of permutation and interval graphs. Congr. Numer., 58:267-275, 1987. Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla., 1987). Google Scholar
  6. Ido Dagan, Martin Charles Golumbic, and Ron Yair Pinter. Trapezoid graphs and their coloring. Discrete Appl. Math., 21(1):35-46, 1988. Google Scholar
  7. Vida Dujmović, Gwenaël Joret, and David R. Wood. An improved bound for First-Fit on posets without two long incomparable chains. SIAM J. Discrete Math., 26(3):1068-1075, 2012. Google Scholar
  8. Thomas Erlebach and Jiri Fiala. On-line coloring of geometric intersection graphs. Comput. Geom., 23(2):243-255, 2002. Google Scholar
  9. Martin Charles Golumbic and Clyde L. Monma. A generalization of interval graphs with tolerances. In Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), volume 35, pages 321-331, 1982. Google Scholar
  10. Martin Charles Golumbic, Doron Rotem, and Jorge Urrutia. Comparability graphs and intersection graphs. Discrete Math., 43(1):37-46, 1983. Google Scholar
  11. Henry A. Kierstead, George F. McNulty, and William T. Trotter, Jr. A theory of recursive dimension for ordered sets. Order, 1(1):67-82, 1984. Google Scholar
  12. Henry A. Kierstead, Stephen G. Penrice, and William T. Trotter, Jr. On-line coloring and recursive graph theory. SIAM J. Discrete Math., 7(1):72-89, 1994. Google Scholar
  13. Henry A. Kierstead, Stephen G. Penrice, and William T. Trotter, Jr. On-line and First-Fit coloring of graphs that do not induce P₅. SIAM J. Discrete Math., 8(4):485-498, 1995. Google Scholar
  14. Henry A. Kierstead and Karin R. Saoub. First-Fit coloring of bounded tolerance graphs. Discrete Appl. Math., 159(7):605-611, 2011. Google Scholar
  15. Henry A. Kierstead and William T. Trotter, Jr. An extremal problem in recursive combinatorics. In Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II (Baton Rouge, La., 1981), volume 33, pages 143-153, 1981. Google Scholar
  16. Seog-Jin Kim, Alexandr Kostochka, and Kittikorn Nakprasit. On the chromatic number of intersection graphs of convex sets in the plane. Electron. J. Combin., 11(1):R52, 2004. Google Scholar
  17. Lásló Lovász. Perfect graphs. In Selected topics in graph theory, 2, pages 55-87. Academic Press, London, 1983. Google Scholar
  18. George Mertzios. The recognition of simple-triangle graphs and of linear-interval orders is polynomial. In Proceedings of the 21st European Symposium on Algorithms (ESA), Sophia Antipolis, France, September 2013, pp. 719-730. Google Scholar
  19. Sriram V. Pemmaraju, Rajiv Raman, and Kasturi Varadarajan. Buffer minimization using max-coloring. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 562-571. ACM, New York, 2004. Google Scholar
  20. Alexandre Rok and Bartosz Walczak. Outerstring graphs are χ-bounded. In Siu-Wing Cheng and Olivier Devillers, editors, 30th Annual Symposium on Computational Geometry (SoCG 2014), pages 136-143. ACM, New York, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact