On-line coloring of geometric intersection graphs

DOI10.1016/S0925-7721(02)00089-5zbMath1008.05053MaRDI QIDQ1862127

Jiří Fiala, Erlebach, Thomas

Publication date: 10 March 2003

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

competitive analysison-line algorithmdisk graphscoloringintersection graphsfirst-fitsquare graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Online coloring of short intervals, Tight bounds for online coloring of basic graph classes, Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors, On distance constrained labeling of disk graphs, On-line approach to off-line coloring problems on graphs with geometric representations, Tight Bounds for Online Coloring of Basic Graph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unit disk graphs
• Coloring inductive graphs on-line
• A special planar satisfiability problem and a consequence of its NP- completeness
• Coin graphs, polyhedra, and conformal mapping
• Unit disk graph recognition is NP-hard
• On-line and first fit colorings of graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Simple heuristics for unit disk graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)