On the Maximum Average Degree and the Incidence Chromatic Number

Acta Scientiarum Naturalium Universitatis Pekinensis

Previous Articles Next Articles

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

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

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

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

Abstract

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

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

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

CLC Number:

O157

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

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

Add to citation manager EndNote|Ris|BibTeX

URL: https://xbna.pku.edu.cn/EN/

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

[1]	BAN Mabao, LUO Peng, Thupten Tsering, Nyima Tashi, CAI Rangjia, YU Yongbin. End-to-End Spanning Tibetan Semantic Role Labeling Based on Graph Parsing [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2025, 61(3): 440-450.
[2]	LUO Wei, LIU Yu, HUANG Qiang, WU Zhihao. Leveraging Graph Structure and Simple Recurrence for Map Matching [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2024, 60(6): 979-988.
[3]	YANG Yizhou, YI Kexin, LI Jiaming, GUO Zhaojie. Late Cenozoic Evolution of Tectonic Geomorphology of the Western Part of the Northern Qaidam Basin: Mid-Pleistocene Uplift Separated the Qaidam and Suganhu Basins [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2024, 60(5): 851-864.
[4]	YANG Hanjun, SUN Min, LOU Xiayin, YANG Shihao. Intelligent Boundary Extraction Method for Large-scale Physical Geographical Objects: Taking Dabie Mountains as an Example [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2024, 60(4): 673-681.
[5]	WU Hui, CHEN Xu, JING Yongjun, WANG Shuyang. MFA-SGWNN: Botnet Detection Based on Multi-Feature Aggregation Spectral Graph Wavelet Neural Network [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2024, 60(3): 403-412.
[6]	XU Yinxin, YANG Zongbao, LIN Yuchen, HU Jinlong, DONG Shoubin. Interpretable Biomedical Reasoning via Deep Fusion of Knowledge Graph and Pre-trained Language Models [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2024, 60(1): 62-70.
[7]	WANG Qing, WANG Wenbo, LI Ying, YANG Yufeng. Genetic Diversity and Phylogenetic Relationship of the Cosmopolitan Bdelloid Rotifer Rotaria sordida [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(5): 719-728.
[8]	LI Yingxue, CHEN Shaohan, ZHENG Weiguo. Knowledge-Driven Interactive Graph Search [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(5): 735-746.
[9]	NING Shuoxian, CHEN Yongshun. Is There an Interconnected Lower Crustal Channel Flow beneath Southeastern Margin of Tibetan Plateau? [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(3): 395-406.
[10]	GAO Yong, MENG Haohan, YE Chao. A Spatially Constraint Negative Sample Generation Method for Geographic Knowledge Graph Embedding [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(3): 434-444.
[11]	ZUO Zhengkang, YAN Lei, SUN Yanbiao, ZHAO Hongying, ZHANG Ruihua, SUN Jiayu, LIU Siyuan, WANG Qiang, SUN Yiyuan. Applicability Study on Parallax Bundle Adjustment in 3D-Photography [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(3): 445-455.
[12]	CHANG Lai-Ho, CHEN Bin. Virtual Field Scene Construction Method Based on Panoramic Photo Inpainting [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(2): 211-220.
[13]	GAO Xiaoqian, ZHOU Xiabing, ZHANG Min. A Multi-information Perception Based Method for Question Answering in Multi-party Conversation [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(1): 21-29.
[14]	LI Yanchu, JING Jiwu, LEI Lingguang, WANG Yuewu, WANG Pingjian. An iRAM-based Light-Weight Cryptographic Algorithm Implementation Scheme against Physical Memory Disclosure Attacks [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(6): 1023-1034.
[15]	WU Jiansheng, QIAN Yun, WANG Hongliang, ZHU Huizhen, WANG Han. Evaluation and Impact Factors of Spatial Supply and Demand of Public Sports Facilities in Shenzhen [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(6): 1101-1110.

On the Maximum Average Degree and the Incidence Chromatic Number

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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics