On-line approach to off-line coloring problems on graphs with geometric representations
From MaRDI portal
Publication:722314
DOI10.1007/s00493-016-3414-xzbMath1399.05077arXiv1402.2437OpenAlexW3099519164MaRDI QIDQ722314
Bartosz Walczak, Tomasz Krawczyk
Publication date: 23 July 2018
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.2437
Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Online algorithms; streaming algorithms (68W27)
Related Items (9)
Improved bounds for colouring circle graphs ⋮ Coloring curves that cross a fixed curve ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ Coloring triangle-free L-graphs with \(O (\log \log n)\) colors ⋮ Online coloring of short intervals ⋮ Box and Segment Intersection Graphs with Large Girth and Chromatic Number ⋮ Conflict-free coloring of string graphs ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Circle graphs are quadratically χ‐bounded
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Triangle-free geometric intersection graphs with large chromatic number
- Triangle-free intersection graphs of line segments with large chromatic number
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- On the chromatic number of multiple interval graphs and overlap graphs
- Comparability graphs and intersection graphs
- Covering and coloring polygon-circle graphs
- Quasi-planar graphs have a linear number of edges
- On geometric graphs with no \(k\) pairwise parallel edges
- On-line chain partitions of orders
- A data structure for dynamic trees
- On-line coloring of geometric intersection graphs
- A triangle-free circle graph with chromatic number 5
- Applications of the crossing number
- Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
- Subtree filament graphs are subtree overlap graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Coloring Clean and K 4-Free Circle Graphs
- On a Coloring Problem.
- Coloring circle graphs
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- On-line and first fit colorings of graphs
- Outerstring graphs are χ-bounded
- Applications of a New Separator Theorem for String Graphs
This page was built for publication: On-line approach to off-line coloring problems on graphs with geometric representations
