Improper colourings of graphs
Improper colourings of graphs
复制标题
图表着色不当
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Ross J. Kang
中科院分区：
文献类型：
--
作者：
Ross J. Kang
我们考虑了图的适当顶点着色的推广，称为不适当着色，其中每个顶点只能与有限数量的t个具有相同颜色的顶点相邻，并且我们在几种不同的设置中研究了这种类型的图着色问题。全文共分为六章。在第一章中，我们概述了以前在不当着色领域的工作。在第2章和第3章中，我们考虑了单位磁盘图的不当着色-这是一个由电信应用驱动的主题-并采用两种方法，首先是算法方法，然后是平均情况分析。在第四章中，我们研究了随机图经典Erdos-Renyi模型的反常色数的渐近性质。在第五章中，我们讨论了有界最大度图的非环反常着色，这是反常着色的一种特殊形式。最后，在第六章中，我们考虑了另一种类型的着色，即节俭着色，在这种着色中，任何颜色在任何邻域中出现的次数都不超过有限次。在整个论文中，我们将观察到行为的梯度：对于随机单元磁盘图和“大”单元磁盘图，相对于适当的着色，我们可以大大减少所需的颜色数量；在Erdos-Renyi随机图中，我们确实获得了一些改进，但只有当t相对较大时；对于有界度图的非环反常色数，我们只在一个很窄的选择范围内发现t的渐近差异。
We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood. Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and "large" unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.