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