Defective and clustered choosability of sparse graphs
Defective and clustered choosability of sparse graphs
复制标题
稀疏图的缺陷和聚类可选择性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
Kevin Hendrey;D. Wood
摘要如果每个单色子图的最大度不超过d，则(广义)图着色有亏数d，如果每个单色分支至多有c个顶点，则(不适当的)图染色有聚簇c。本文研究了给定最大平均度的图的亏表着色和簇表着色问题。我们证明了每个最大平均度小于(2d+2)/(d+2)k的图是k-可选的，且有缺陷d。这改进了Havet和Sereni的类似结果(J·图论，2006)。对于平均度最大为m的图的聚簇可选性，以前没有关于颜色个数的(1-ɛ)m的界。上述d=1的结果解决了这个问题。它意味着每个具有最大平均度m的图都是$lFloor{frac{3}{4}m+1}
Floor$-可选，聚类2。这将Kopreski和Yu(离散数学，2017)的结果推广到可选设置。然后，我们证明了两个关于聚类性的结果，这两个结果探索了颜色数量和聚类性之间的权衡。特别地，我们证明了具有最大平均度m的每个图都是$lFloor{frac{7}{10}m+1}。
Floor$-可选择群集9，并且是$lFloor{frac{2}{3}m+1}
楼层$-可选择群集O(M)。作为一个例子，后者的结果表明，每个二平面图都是8-可选的，具有有界聚类。这是地球-月球问题的集群版本的最著名的结果。结果推广到我们只考虑至少具有一定数量顶点的子图的最大平均度的设置。文中给出了几个应用实例。
Abstract An (improper) graph colouring has defect d if each monochromatic subgraph has maximum degree at most d, and has clustering c if each monochromatic component has at most c vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than (2d+2)/(d+2)k is k-choosable with defect d. This improves upon a similar result by Havet and Sereni (J. Graph Theory, 2006). For clustered choosability of graphs with maximum average degree m, no (1-ɛ)m bound on the number of colours was previously known. The above result with d=1 solves this problem. It implies that every graph with maximum average degree m is $lfloor{frac{3}{4}m+1}
floor$-choosable with clustering 2. This extends a result of Kopreski and Yu (Discrete Math., 2017) to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree m is $lfloor{frac{7}{10}m+1}
floor$-choosable with clustering 9, and is $lfloor{frac{2}{3}m+1}
floor$-choosable with clustering O(m). As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth–moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.