• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >A refinement of choosability of graphs
【24h】

A refinement of choosability of graphs

机译：改进图形的可选择性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Assume k is a positive integer, lambda = {k(1), k(2),... , k(q)} is a partition of k and G is a graph. A lambda-list assignment of G is a k-list assignment L of G such that the colour set boolean OR(v is an element of V(G)) L(v) can be partitioned into q subsets C-1 boolean OR C-2 ... boolean OR C-q and for each vertex v of G, vertical bar L(v) boolean AND C-i vertical bar = k(i). We say G is lambda-choosable if for each lambda-list assignment L of G, G is L-colourable. It follows from the definition that if lambda = {k}, then lambda-choosable is the same as k-choosable, if lambda = {1, 1, ... , 1}, then lambda-choosable is equivalent to k-colourable. For the other partitions of k sandwiched between {k} and {1, 1, ... , 1} in terms of refinements, lambda-choosability reveals a complex hierarchy of colourability of graphs. We prove that for two partitions lambda, lambda' of k, every lambda-choosable graph is lambda'-choosable if and only if lambda' is a refinement of lambda. Then we study lambda-choosability of special families of graphs. The Four Colour Theorem says that every planar graph is {1, 1, 1, 1}-choosable. A very recent result of Kemnitz and Voigt implies that for any partition lambda of 4 other than {1, 1, 1, 1}, there is a planar graph which is not lambda-choosable. We observe that, in contrast to the fact that there are non-4-choosable 3-chromatic planar graphs, every 3-chromatic planar graph is {1, 3}-choosable, and that if G is a planar graph whose dual G* has a connected spanning Eulerian subgraph, then G is {2, 2}-choosable. We prove that if n is a positive even integer, lambda is a partition of in which each part is at most 3, then K-n is edge lambda-choosable. Finally we study relations between lambda-choosability of graphs and colouring of signed graphs and generalized signed graphs. A conjecture of Macajova, Raspaud and Skoviera that every planar graph is signed 4-colcourable is recently disproved by Kardos and Narboni. We prove that every signed 4-colourable graph is weakly 4-choosable, and every signed Z(4)-colourable graph is {1, 1, 2}-choosable. The later result combined with the above result of Kemnitz and Voigt disproves a conjecture of Kang and Steffen that every planar graph is signed Z(4)-colourable. We shall show that a graph constructed by Wegner in 1973 is also a counterexample to Kang and Steffen's conjecture, and present a new construction of a non-{1, 3}-choosable planar graphs. (C) 2019 Elsevier Inc. All rights reserved.
机译：假设K是正整数，Lambda = {k（1），k（2），...，k（q）}是k和g的分区是图。 g的lambda列表分配是g的k列表分配l，使得颜色设置布尔值或（v是v（g）的元素）l（v）可以被划分为q子集c-1布尔值或c -2 ...布尔或CQ以及G的每个顶点V，垂直条L（V）布尔和CI垂直条= K（i）。我们说g是λ-可选择的，如果每个Lambda列表分配L的G，G是L-的COLOURABLE。从定义中，如果Lambda = {k}，那么λ-选择与k-choosable相同，如果lambda = {1,1，......，1}，则λ-choosable相当于k-污染。对于在细化方面夹在{k}和{1,1，...，1}之间的k的其他分区，Lambda可选择性揭示了图形的复杂层次结构。我们证明，对于k的两个分区，每个λ-choosable图表是λ-choosable，如果λ'是兰姆达的改进。然后我们研究特殊图形的Lambda可选择性。四种颜色定理表明每个平面图都是{1,1,1,1，1}摘要。 Kemnitz和Voigt的最近结果意味着对于其他4个除{1,1,1,1，1}的任何分区Lambda，都有一个不是λ-可选择的平面图。我们观察到，与存在非4个可选择的3-彩色平面图的事实相比，每个3色平面图是{1,3} - ofcoosable，如果g是惯性图形的平面图有一个连接的跨越欧拉的子图，那么g是{2,2}的摘要。我们证明，如果n是正甚至整数，则Lambda是每个部分最多3的分区，然后K-N是边缘λ-choosable。最后，我们研究了图形的λ-可选择性与签名图的着色和广义签名图之间的关系。 Macajova，Raspaud和Skoviera的猜想，每个平面图都签署了4-洋葱，最近被Kardos和Narboni所吸引。我们证明，每个符号的4个可染色图都是弱4可选择的，并且每个符号z（4） - 浅色图形是{1,1,2} - ocoosable。后来的结果与Kemnitz和Voigt的上述结果相结合，使康复和Steffen的猜想相结合，即每个平面图都是签名Z（4）-Colourable的z（4）。我们将表明1973年由Wegner构建的图表也是康和Steffen的猜想的一个反例，并且呈现了非{1,3}的新建结构。 （c）2019 Elsevier Inc.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号