Improper colouring of (random) unit disk graphs

DOI10.1016/j.disc.2007.07.070zbMath1135.05021OpenAlexW2129414351MaRDI QIDQ2476286

Tobias Müller, Jean-Sébastien Sereni, Ross J. Kang

Publication date: 18 March 2008

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2007.07.070

zbMATH Keywords

channel assignmentrandom geometric graphunit disk graphimproper colouring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Note on coloring of double disk graphs ⋮ The t-Improper Chromatic Number of Random Graphs ⋮ Improper coloring of unit disk graphs ⋮ Unnamed Item ⋮ Bounds and fixed-parameter algorithms for weighted improper coloring ⋮ Defective Coloring on Classes of Perfect Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unit disk graphs
• Colouring proximity graphs in the plane
• Extremal results on defective colorings of graphs
• A note on generalized chromatic number and generalized girth
• Defective coloring revisited
• Improper Colourings of Unit Disk Graphs
• The t-improper chromatic number of random graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Approximation schemes for covering and packing problems in image processing and VLSI
• A note on defective colorings of graphs in surfaces
• List Improper Colourings of Planar Graphs
• Acrylic improper colorings of graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Random Geometric Graphs
• Robust algorithms for restricted domains
• Focusing of the scan statistic and geometric clique number
• Random channel assignment in the plane
• Improper choosability of graphs and maximum average degree
• Graph-Theoretic Concepts in Computer Science