2011/10/19 by Rosalie Carlson, Stephen Flood, Carlson, Rosalie +5
Computer Science · Mathematics · #05C75 #91B12 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C75 #msc:91B12
paper · pdf · doi:10.48550/arxiv.1110.4205
18 pages, 8 figures, related papers at http://www.math.hmc.edu/~su/papers.html
arxiv created 2011/10/19 · arxiv updated 2011/10/20
A circular arc graph is the intersection graph of a collection of connected arcs on the circle. We solve a Tur'an-type problem for circular arc graphs: for n arcs, if m and M are the minimum and maximum number of arcs that contain a common point, what is the maximum number of edges the circular arc graph can contain? We establish a sharp bound and produce a maximal construction. For a fixed m, this can be used to show that if the circular arc graph has enough edges, there must be a point that is covered by at least M arcs. In the case m=0, we recover results for interval graphs established by Abbott and Katchalski (1979). We suggest applications to voting situations with interval or circular political spectra.