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

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

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

王淑栋^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.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://xbna.pku.edu.cn/CN/

https://xbna.pku.edu.cn/CN/Y2008/V44/I5/727

[1]	班玛宝, 罗鹏, 头旦才让, 尼玛扎西, 才让加, 于永斌. 基于图解析的端到端片段藏文语义角色标注方法[J]. 北京大学学报自然科学版, 2025, 61(3): 440-450.
[2]	周治岐, 李培军. 利用光谱–空间聚类的多光谱图像岩性分类[J]. 北京大学学报自然科学版, 2025, 61(3): 525-534.
[3]	左正康, 董娇娇, 张斌, 张玲. 摄影测量共线方程参数化方法综述[J]. 北京大学学报自然科学版, 2025, 61(3): 608-616.
[4]	罗威, 刘钰, 黄强, 武志昊. 融合图结构学习和轻量级循环建模的地图匹配方法[J]. 北京大学学报自然科学版, 2024, 60(6): 979-988.
[5]	蒋建斌, 黄松, 吴建国. 基于图像分割技术的智能造字研究[J]. 北京大学学报自然科学版, 2024, 60(6): 989-1000.
[6]	杨涵珺, 孙敏, 楼夏寅, 杨仕浩. 大尺度自然地理实体边界智能化提取方法——以大别山为例[J]. 北京大学学报自然科学版, 2024, 60(4): 673-681.
[7]	金之钧, 张川. 面向碳中和的中国能源转型路径思考[J]. 北京大学学报自然科学版, 2024, 60(4): 767-774.
[8]	吴悔, 陈旭, 景永俊, 王叔洋. MFA-SGWNN: 基于多特征聚合谱图小波神经网络的僵尸网络检测[J]. 北京大学学报自然科学版, 2024, 60(3): 403-412.
[9]	徐寅鑫, 杨宗保, 林宇晨, 胡金龙, 董守斌. 基于知识图谱和预训练语言模型深度融合的可解释生物医学推理[J]. 北京大学学报自然科学版, 2024, 60(1): 62-70.
[10]	王瑞, 梁建国, 花嵘. 基于多尺度特征解析的放射学报告生成方法[J]. 北京大学学报自然科学版, 2024, 60(1): 71-78.
[11]	周伯瀚, 曹健, 王源. 基于Transformer模型的手写数学公式语法树解码器[J]. 北京大学学报自然科学版, 2023, 59(6): 909-914.
[12]	李映雪, 陈劭涵, 郑卫国. 知识驱动的交互式图搜索[J]. 北京大学学报自然科学版, 2023, 59(5): 735-746.
[13]	刘相呈, 曹健, 姚宏毅, 徐鹏涛, 张袁, 王源. 基于自适应剪枝率与高效权重继承的神经网络通道剪枝方法[J]. 北京大学学报自然科学版, 2023, 59(5): 764-772.
[14]	杨欣宇, 李培军. 综合利用光谱特征、形态学特征和霍夫变换的无人机图像玉米幼苗分布信息提取[J]. 北京大学学报自然科学版, 2023, 59(5): 843-853.
[15]	高勇, 孟浩瀚, 叶超. 基于空间约束的地理知识图谱嵌入表示的负样本生成方法[J]. 北京大学学报自然科学版, 2023, 59(3): 434-444.