Improper colouring of (random) unit disk graphs

DOI10.1016/J.DISC.2007.07.070zbMATH Open1135.05021OpenAlexW2129414351MaRDI QIDQ2476286FDOQ2476286

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

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

Recommendations

• Improper colouring of (random) unit disk graphs
• Improper coloring of unit disk graphs
• The t-improper chromatic number of random graphs
• The \(t\)-improper chromatic number of random graphs
• Improper C-colorings of graphs

zbMATH Keywords

random geometric graphchannel assignmentunit disk graphimproper colouring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Improper C-colorings of graphs
• Improper coloring of unit disk graphs
• Defective Coloring on Classes of Perfect Graphs
• Bounds and fixed-parameter algorithms for weighted improper coloring
• Improper colouring of (random) unit disk graphs
• Note on coloring of double disk graphs
• The \(t\)-improper chromatic number of random graphs
• Parameterized complexity of fair vertex evaluation problems

This page was built for publication: Improper colouring of (random) unit disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476286)