...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >F-WORM colorings: Results for 2-connected graphs
【24h】

F-WORM colorings: Results for 2-connected graphs

机译：F-WORM染色：2连接图的结果

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

摘要

Given two graphs F and G, an F-WORM coloring of G is an assignment of colors to its vertices in such a way that no F-subgraph of G is monochromatic or rainbow. If G has at least one such coloring, then it is called F-WORM colorable and W-(G, F) denotes the minimum possible number of colors. Here, we consider F-WORM colorings with a fixed 2-connected graph F and prove the following three main results: (1) For every natural number k, there exists a graph G which is F-WORM colorable and W-(G, F) = k; (2) It is NP-complete to decide whether a graph is F-WORM colorable; (3) For each k >= vertical bar V(F)vertical bar -1, it is NP-complete to decide whether a graph G satisfies W-(G, F) <= k. This remains valid on the class of F-WORM colorable graphs of bounded maximum degree. We also prove that for each n >= 3, there exists a graph G and integers r and s such that s >= r + 2, G has K-n-WORM colorings with exactly r and also with s colors, but it admits no K-n-WORM colorings with exactly r + 1, . . . , s - 1 colors. Moreover, the difference s - r can be arbitrarily large. (C) 2017 Elsevier B.V. All rights reserved.
机译：给定两个曲线图F和G，G的F-Vorm着色是以这种方式分配颜色，使得G的F形状或彩虹的F形状或彩虹。如果G具有至少一个这样的着色，则它被称为F-蠕虫可色，并且W-（G，F）表示最小可能的颜色数。在这里，我们考虑具有固定的2连接图F的F-WORM着色，并证明以下三个主要结果：（1）对于每个天然数K，存在图G是F-蠕虫可调和W-（G， f）= k; （2）确定图形是否为F-WORM可色; （3）对于每个k> =垂直条V（f）垂直条-1，它是np-chequess以确定图G是否满足W-（g，f）<= k。这对界最大程度的F-Vorm可色图类仍然有效。我们还证明，对于每个n> = 3，存在图G和整数R，S> = R + 2，G具有kn-蠕虫着色，恰好R，也具有S的颜色，但它承认没有kN - 污迹着色，恰好R + 1，。 。 。 ，s - 1种颜色。此外，差异S-R可以任意大。 （c）2017 Elsevier B.v.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号