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]. 北京大学学报（自然科学版）.

[1]	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.
[2]	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.
[3]	LI Yingxue, CHEN Shaohan, ZHENG Weiguo. Knowledge-Driven Interactive Graph Search [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2023, 59(5): 735-746.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	BI Chunqing, LIU Yan, GUO Wenjing, JIANG Xilin, LI Zhengguoshen, XU Nan. Physiological and Biochemical Responses of Corbicula fluminea under the Stress of Graphene Oxide Combined with Perfluorooctane Sulfonate (PFOS) [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(4): 721-729.
[12]	LIN Chiumei, SONG Shuguang, CUI Ying. Abiotic Methane Inclusions in Olivine from the Yushigou Peridotite and Their Forming Conditions [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(2): 241-248.
[13]	XU Yang, JIANG Yuru, ZHANG Yuyao, HE Weikai. Research on Dialogue Entity Relation Extraction with Enhancing Character Information [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(1): 13-20.
[14]	HUANG Jin, XU Shi, CAI Ercong, WU Zhijie, GUO Meimei, ZHU Jia. An Emotion-Cause Pair Extraction Model Based on Multichannel Compact Bilinear Pooling [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(1): 21-28.
[15]	LIAO Yiming, OUYANG Chunping, LIU Yongbin, HU Fuyu. Drug-Target Interactions Prediction Based on Meta-path of Heterogeneous Information Network [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2022, 58(1): 37-44.

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