Improper coloring of unit disk graphs

DOI10.1002/net.20318zbMath1207.05056MaRDI 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 lattice; interval graph; hexagonal graph; unit disk graph; improper coloring; defective coloring; weighted coloring

Mathematics Subject Classification ID

05C90: Applications of graph theory

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

On t-relaxed chromatic number of r-power paths, Unnamed Item, Parameterized (Approximate) Defective Coloring, Defective Coloring on Classes of Perfect Graphs, Maximum dissociation sets in subcubic trees, Note on coloring of double disk graphs, Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, Dynamic \(F\)-free coloring of graphs, On \(t\)-relaxed 2-distant circular coloring of graphs, An improved approximation for maximum \(k\)-dependent set on bipartite graphs, Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree, 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, Channel assignment problem and relaxed 2-distant coloring of graphs, IMPROPER COLORING OF WEIGHTED GRID AND HEXAGONAL GRAPHS, Unnamed Item, Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in 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