直径为2的图的P2路色问题

• 作者: 李瑾 洪百会
• 来源期刊: 沈阳建筑工程学院学报(自然科学版)
• 学科: 数学
• 关键词: 图 着色 路色数 刻划
• 年，卷（期）: 2003,（1）
• 所属期刊栏目: 基础科学
• 页码范围: 75-77
• 页数: 3页
• 分类号: O157.5
• 字数: 2878字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-2021.2003.01.023

摘要

针对以r为参数的直径为2的图的(2,r)路色数的计算复杂性问题,从直径为2的图及任意给定的整数r≥3,图的(2,r)路色数问题是NP-完全的入手,给出直径为2的(2,2)的路色图的一个好的刻划,并由此给出该问题一个多项式时间算法,从而解决了以r为参数的直径为2的图的(2,r)路色数问题的计算复杂性分类.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李瑾	沈阳工业学院基础部	1	0	0.0	0.0
2	洪百会		3	7	2.0	2.0