Improper colouring of (random) unit disk graphs

DOI10.1016/J.DISC.2007.07.070MaRDI QIDQ2476286zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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
• Note on coloring of double disk graphs
• Improper colouring of (random) unit 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)