A vertex set U is complete to X is everyvertex in U is complete to X. A vertex v is complete to some vertex set X if every vertex in X is adjacent to v. We denote the chromatic numberby χ ( G ), and define χ ( G ), the clique partition number, to be the chromaticnumber of the completement of G. The size of the largest clique is denoted by ω ( G ), while the size of thelargest stable set is α ( G ), the stability of G. A stable set of G is a subgraph or vertex set so that no two vertices areadjacent. A clique of G is a subgraph in which any two vertices areadjacent. For general graph-theoretic notation and concepts we refer to Diestel. In Section 4 we will discuss which geometricinsights will be exploited. The key lemma on which the proof of Theorem 2rests will be deferred to Section 5. After briefly stating some of the basicdefinitions that we are going to use we will proceed with the proof of our mainresult, Theorem 2, in Section 3. We referto Balasundaram and Butenko for a survey on several optimisation problemsin udg s.The paper is organised as follows. whogive a 3-approximation colouring algorithm and the result by Clark, Colbournand Johnson that 3-colourability remains NP-complete for udg s. Optimisation problems in udg s, and in particular, colouring udg s algorith-mically have attracted some attention. Finally,considering fractional instead of ordinary colourings, Gerke and McDiarmid prove that the fractional chromatic number is bounded by 2. In that context,it turns out that with high probability the chromatic number is very close to theclique number, much closer even than the factor of of the lower bound. Another piece of evidence is provided by McDiarmid, whoinvestigates fairly general models of random unit disk graphs. McDiarmid and Reed show that these can be coloured with at most ω +13 colours. The second classconsists of augmentations of induced subgraphs of the triangular lattice in theplane. Thefirst of these is the class of triangle-free udg s: A triangle-free udg is planar,see Breu, and thus by Gr¨otzsch’ theorem 3-colourable. There are two classes of udg s,for which it is known that their chromatic number is bounded by ω. ω than to Peeters’ bound.There is some more evidence for this belief. In this article, we will prove thatthe lower bound is the true one if the unit disk graph has, in addition, at moststability two: Theorem 2.Ī unit disk graph G with α ( G ) ≤ can be coloured with at most ω ( G ) colours. Clearly, between an upper bound of essentially 3 ω and a lower bound of ω there is quite a bit of scope for improvement. Moreover, we see that C k k − has stability α = 2 andclique number ω = k, from which we deduce for the chromatic number that χ ( C k k − ) ≥ k − = ω −. Observe that we may realise any C kn as a unit disk graph by placing the vertices at equidistance on a circleof appropriate radius. , n − i and j are adjacent if | i − j | ≤ k −ġ. Consider the class of graphs C kn on vertex set 0. How good is that bound? Malesi´nska, Piskorz and Weißenfels gave thefollowing lower bound. A unit disk graph G can be coloured with at most ω ( G ) − colours. Unit disk graphs distinguish themselves from general graphsin that their chromatic number can be upper-bounded in terms of the cliquenumber. The frequency assignment problem then becomes a graphcolouring problem, and naturally, it is desired to assign as few frequencies aspossible.In this article I will treat the colouring of a unit disk graph from a structuralpoint of view. Anedge between two points is understood as the devices being close enough tointerfere with each other, so that an assigned frequency corresponds to a stableset in the graph. There, the task is to assign different frequencies to the wireless devicesin order for them to communicate with a base station without interference. One of the earliest application isdue to Hale who considered them in the context of the frequency assignmentproblem. As a very basic model for wireless devices, unit disk graphs as well asmore sophistacted variants have attracted quite a lot of interest, and thereexists an extensive literature on their subject. A unit disk graph (or udg for short) is defined on a point set in the plane,where two points are considered as adjacent vertices if their distance is at mostone. We prove that every stability two unit disk graph has chromatic num-ber at most times its clique number. S e p Colouring stability two unit disk graphs
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |