Improper coloring of unit disk graphs

DOI10.1002/net.20318zbMath1207.05056OpenAlexW4256347034MaRDI QIDQ3057115

Frédéric Havet, Jean-Sébastien Sereni, Ross J. Kang

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20318

zbMATH Keywords

triangular latticeinterval graphhexagonal graphunit disk graphimproper coloringdefective coloringweighted coloring

Mathematics Subject Classification ID

Applications of graph theory (05C90) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Dynamic \(F\)-free coloring of graphs ⋮ Unnamed Item ⋮ Parameterized (Approximate) Defective Coloring ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ Maximum dissociation sets in subcubic trees ⋮ Graph partitions under average degree constraint ⋮ Minimum number of maximal dissociation sets in trees ⋮ Note on coloring of double disk graphs ⋮ On t-relaxed chromatic number of r-power paths ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments ⋮ The complexity of dissociation set problems in graphs ⋮ Unnamed Item ⋮ IMPROPER COLORING OF WEIGHTED GRID AND HEXAGONAL GRAPHS ⋮ On \(t\)-relaxed 2-distant circular coloring of graphs ⋮ An improved approximation for maximum \(k\)-dependent set on bipartite graphs ⋮ Channel assignment problem and relaxed 2-distant coloring of graphs ⋮ Defective Coloring on Classes of Perfect Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List colourings of planar graphs
• An optimal greedy heuristic to color interval graphs
• Unit disk graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Every planar graph is 5-choosable
• On coloring unit disk graphs
• Improper colouring of (random) unit disk graphs
• Defective coloring revisited
• Improper Colourings of Unit Disk Graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• List Improper Colourings of Planar Graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Robust algorithms for restricted domains
• Channel assignment and weighted coloring
• Simple heuristics for unit disk graphs
• Random channel assignment in the plane
• Static frequency assignment in cellular networks