图的最大平均度与关联色数

北京大学学报（自然科学版）

图的最大平均度与关联色数

王淑栋^1,2,闫立军²,刘向荣¹

¹北京大学信息科学技术学院软件所，北京100871;²山东科技大学信息科学与工程学院,青岛266510;

收稿日期:2007-09-06 出版日期:2008-09-20 发布日期:2008-09-20

On the Maximum Average Degree and the Incidence Chromatic Number

WANG Shudong^１，２ YAN Lijun^２ LIU Xiangrong^１

¹Institute of Software,School of Electronic Engineering and Computer Science,Peking University,Beijing 100871; ²College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao 266510;

Received:2007-09-06 Online:2008-09-20 Published:2008-09-20

摘要/Abstract

摘要： 图G的关联着色是从关联集I(G)到颜色集C的一个映射使得任意两个相邻的关联不着同色。从图的结构性质出发,对图的关联着色进行了讨论，利用归纳法和换色技巧证明了mad(G)<3,Δ(G)=4的图G存在一个(6,2)-关联着色。

关键词: 图, 关联着色, 关联色数, 最大平均度

Abstract: An incidence coloring of graph G is a mapping from the incidence set I(G) to color set C such that any two neighborly incidences are assigned different colors The authors discussed incidence coloring of graph and proved graph G with mad(G)<3,Δ(G)=4 to admit a (6,2)-incidence coloring by the induction and the exchanging colors method from the aspect of configuration property

Key words: graph, incidence coloring, incidence chromatic number, maximum average degree

中图分类号:

O157

王淑栋,闫立军,刘向荣. 图的最大平均度与关联色数[J]. 北京大学学报（自然科学版）.

WANG Shudong,YAN Lijun,LIU Xiangrong. On the Maximum Average Degree and the Incidence Chromatic Number[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

[1]	徐寅鑫, 杨宗保, 林宇晨, 胡金龙, 董守斌. 基于知识图谱和预训练语言模型深度融合的可解释生物医学推理[J]. 北京大学学报自然科学版, 2024, 60(1): 62-70.
[2]	王瑞, 梁建国, 花嵘. 基于多尺度特征解析的放射学报告生成方法[J]. 北京大学学报自然科学版, 2024, 60(1): 71-78.
[3]	周伯瀚, 曹健, 王源. 基于Transformer模型的手写数学公式语法树解码器[J]. 北京大学学报自然科学版, 2023, 59(6): 909-914.
[4]	李映雪, 陈劭涵, 郑卫国. 知识驱动的交互式图搜索[J]. 北京大学学报自然科学版, 2023, 59(5): 735-746.
[5]	刘相呈, 曹健, 姚宏毅, 徐鹏涛, 张袁, 王源. 基于自适应剪枝率与高效权重继承的神经网络通道剪枝方法[J]. 北京大学学报自然科学版, 2023, 59(5): 764-772.
[6]	杨欣宇, 李培军. 综合利用光谱特征、形态学特征和霍夫变换的无人机图像玉米幼苗分布信息提取[J]. 北京大学学报自然科学版, 2023, 59(5): 843-853.
[7]	高勇, 孟浩瀚, 叶超. 基于空间约束的地理知识图谱嵌入表示的负样本生成方法[J]. 北京大学学报自然科学版, 2023, 59(3): 434-444.
[8]	张赖和, 陈斌. 基于全景图像的虚拟野外场景构建方法[J]. 北京大学学报自然科学版, 2023, 59(2): 211-220.
[9]	周嵘, 吴朝东, 张亚楠. 基于生成对抗网络的砂岩薄片图像视野外重建[J]. 北京大学学报自然科学版, 2023, 59(2): 231-241.
[10]	蒋彦廷. 依据《中国图书馆分类法》的英文图书分类探索[J]. 北京大学学报自然科学版, 2023, 59(1): 11-20.
[11]	高晓倩, 周夏冰, 张民. 基于多信息感知的多方对话问答方法[J]. 北京大学学报自然科学版, 2023, 59(1): 21-29.
[12]	徐鹏涛, 曹健, 孙文宇, 李普, 王源, 张兴. 基于可融合残差卷积块的深度神经网络模型层剪枝方法[J]. 北京大学学报自然科学版, 2022, 58(5): 801-807.
[13]	徐鹏涛, 曹健, 陈玮乾, 刘晟荣, 王源, 张兴. 基于离群值去除的卷积神经网络模型训练后量化预处理方法[J]. 北京大学学报自然科学版, 2022, 58(5): 808-812.
[14]	徐洋, 蒋玉茹, 张禹尧, 何威恺. 融合角色指代的多方对话关系抽取方法研究[J]. 北京大学学报自然科学版, 2022, 58(1): 13-20.
[15]	黄晋, 许实, 蔡而聪, 吴志杰, 郭美美, 朱佳. 基于多通道压缩双线性池化的情感‒原因句子对提取模型[J]. 北京大学学报自然科学版, 2022, 58(1): 21-28.