The chromatic and clique numbers of random scaled sector graphs
type: Item
instance of: scholarly article
title: The chromatic and clique numbers of random scaled sector graphs
zbMATH Open document ID: 1085.05028
author: Vishal Sanwalani
author: J. Díaz
author: Maria Serna
author: P. G. Spirakis
published in: Theoretical Computer Science
publication date: 2006-03-20T00:00:00Z
review text: In the unit square, \(n\) random points are chosen that are independently and uniformly distributed. At each point a sector is drawn with radius depending on \(n\) and with a fixed angle different from 180 degrees. The directions of the sectors are given by independent uniformly distributed orientation angles. The random sector graph \(G\) is defined as a digraph on the \(n\) points with an arc from point \(i\) to point \(j\) if and only if point \(j\) belongs to the sector from point \(i\). The chromatic number and the sizes of the maximum directed and undirected cliques of \(G\) are investigated. Asymptotic results are given as \(n\) tends to infinity.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 57M15
zbMATH DE Number: 5013293
zbMATH Keywords: Random geometric graphs
zbMATH Keywords: chromatic number
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.09.050
OpenAlex ID: W1964080736
cites work: Unit disk graphs
cites work: Random channel assignment in the plane
cites work: Q4250147
cites work: Random Geometric Graphs
DOI: 10.1016/J.TCS.2005.09.050
description: scientific article; zbMATH DE number 5013293