关于图的L(3,2,1)-标号问题

• 作者: 刘家壮 邵振东
• 来源期刊: 应用数学
• 学科: 数学
• 关键词: L(3,2,1)-标号 顶点2-着色 2-色数
• 年，卷（期）: 2004,（4）
• 页码范围: 596-602
• 页数: 7页
• 分类号: O157.5
• 字数: 1916字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9847.2004.04.016

摘要

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x).使得若d(x,y)＝1.则 |f(x)-f(y)|≥2;若d(x,y)＝2,则 |f(x)-f(y)|≥1.图G的L(2,1)标号数λ(G)是使得G有max{f(v):v∈V(G)}=k的L(2,1)标号中的最小数k.本文将L(2,1)-标号问题推广到更一般的情形即L(3,2,1)-标号问题.我们首先定义了图G的顶点3-着色及图的3-色数χ3(G)等有关概念,并推导出3-色数χ3(G)的上界;然后根据χ3(G)与λ3(G)的关系,得出了对一般图G,有λ3(G)≤3(maxδH( )G(H))(△2-△+1)这一一般关系式;最后证明了对一般平面图G,有λ3(G)≤15(△2-△+1),并得出了其它几类平面图的λ3(G)的上界.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邵振东	南京大学数学系	12	18	3.0	3.0
2	刘家壮	山东大学数学研究所	55	329	10.0	15.0