不含3K1+K2和C4为导出子图的图的色数

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (19): 50-52.

不含3K1+K2和C4为导出子图的图的色数

王晓，汪小黎

商洛学院数学与计算机应用学院，陕西商洛 726000

出版日期:2015-09-30 发布日期:2015-10-13

On chromatic number of {3K1+K2,C4}-free graphs

WANG Xiao, WANG Xiaoli

College of Mathematics and Computer Application, Shangluo University, Shangluo, Shannxi 726000

Online:2015-09-30 Published:2015-10-13

摘要/Abstract

摘要： Gyárfás曾猜想：对于每一个不含森林[F]作为导出子图的图[G]，存在整数函数[f(F,ω(G))]使得[χ(G)f(F,ω(G))]，其中[χ(G)]和[ω(G)]分别表示图的色数和团数。以强完美图定理为基础，通过对不含[3K1+K2]和[C4]作为导出子图的图的结构进行分析，根据图的独立数进行分类讨论，得到该类图色数的关于团数线性函数的表达式的上界。

关键词: 色数, 限制子图, [&chi, ]-界函数, 完美图

Abstract: Gyárfás conjured that for a given forest[F], there exists an integer function[f(F,ω(G))] such that [χ(G)f(F,ω(G))] for any[F]-free graph [G], where [χ(G)] and [ω(G)] are the chromatic number and clique number of [G], respectively. By the strong perfect graph theorem, the structural characterization of[{3K1+K2,?C4}]-free graphs is analyzed, according to classification for independent number of graphs, the upper bound, with linear function in term of clique number, on chromatic number of [{3K1+K2,?C4}]-free graphs is obtained.

Key words: chromatic number, forbidden subgraph, [χ]-bound function, perfect graph

王晓，汪小黎. 不含3K1+K2和C4为导出子图的图的色数[J]. 计算机工程与应用, 2015, 51(19): 50-52.

WANG Xiao, WANG Xiaoli. On chromatic number of {3K1+K2,C4}-free graphs[J]. Computer Engineering and Applications, 2015, 51(19): 50-52.

[1]	刘莉萍1，章新友1，牛晓录2，郭永坤1，丁亮1. 基于Spark的并行关联规则挖掘算法研究综述[J]. 计算机工程与应用, 2019, 55(9): 1-9.
[2]	李艳，张欣. 外1-平面图的均匀边染色[J]. 计算机工程与应用, 2019, 55(24): 37-40.
[3]	郭红，周健倩，张瑛瑛，郭昆. 基于协处理器的HBase二级索引方法[J]. 计算机工程与应用, 2019, 55(21): 87-92.
[4]	苏庆，汤毅豪，曾永安，刘添添，郑力明. 单链结构实时识别及可视化布局算法研究[J]. 计算机工程与应用, 2019, 55(16): 240-245.
[5]	吴进，赵隽，李聪，吴汉宁. 机器视觉中边缘检测算法的SDSoC加速实现[J]. 计算机工程与应用, 2019, 55(12): 208-214.
[6]	薛伟，陈璟，张熠. 基于深度学习的Wi-Fi与iBeacon融合的室内定位方法[J]. 计算机工程与应用, 2019, 55(1): 29-34.
[7]	陈志旺1，黄兴旺2，陈志兴3，赵子铮2，黄丽芳4. 区间多目标优化非支配排序云模型算法[J]. 计算机工程与应用, 2017, 53(22): 143-149.
[8]	毋笑蓉1，师智斌1，雷海卫2，杜博1. 基于随机森林分类的HEVC帧内CU快速划分算法[J]. 计算机工程与应用, 2017, 53(21): 115-120.
[9]	江红豆，李敬文，曹道通，江世明. 随机图的邻点可区别VI-均匀全染色算法[J]. 计算机工程与应用, 2017, 53(15): 41-46.
[10]	胡腾云，尹波，代素敏，李敬文. 随机图的点可区别V-全染色算法[J]. 计算机工程与应用, 2015, 51(16): 26-29.
[11]	田京京. 若干多重Mycielski图的邻点可区别I-全色数[J]. 计算机工程与应用, 2012, 48(25): 39-41.
[12]	李凯，王兰. 层次聚类的簇集成方法研究[J]. 计算机工程与应用, 2010, 46(27): 120-123.
[13]	范彩霞,吴宁. 图形处理器光照引擎的设计[J]. 计算机工程与应用, 2009, 45(7): 86-88.
[14]	靳勇,白光伟. Kalman滤波的自适应链路层FEC控制策略[J]. 计算机工程与应用, 2009, 45(7): 129-134.
[15]	王尔申,张淑芳,胡青. 嵌入式GPS接收机系统的FPGA配置方法研究[J]. 计算机工程与应用, 2009, 45(4): 86-88.