北大中文核心期刊
中国科学引文数据库（CSCD）来源期刊
中国科技核心期刊
入选数学领域高质量科技期刊
Scopus
EBSCO 

运筹学学报 >

2026 , Vol. 30 >Issue 2: 232 - 236

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2026.02.018

不含F5作为子图的平面图的边染色

  • 薛玲 ,
  • 吴建良
展开
  • 1. 泰山职业技术学院信息技术工程系, 山东 泰安 271000;
    2. 山东大学数学学院, 山东 济南 250100

收稿日期: 2024-05-06

  网络出版日期: 2026-06-12

基金资助

国家自然科学基金 (No. 11971270)

收起

Edge colorings of planar graphs without 5-fans

  • XUE Ling ,
  • WU Jianliang
Expand
  • 1 Department of Information Engineering, Taishan Polytechnic, Taian 271000, Shandong, China;
    2 School of Mathematics, Shandong University, Jinan 250100, Shandong, China

Received date: 2024-05-06

  Online published: 2026-06-12

Fold

摘要

图的$k$-边染色是指用$k$种颜色对它的边进行染色使得相邻的两条边染不同色,用$\chi'(G)$来记图$G$获得这个染色的最小的$k$值。本文证明了:若平面图$G$不含点数为$5$的扇图$F_5$作为子图,则$\chi'(G)\leq\max\{6,\Delta (G)\}$。

关键词： 边染色; 平面图; 圈

本文引用格式

薛玲 , 吴建良 . 不含F5作为子图的平面图的边染色[J]. 运筹学学报, 2026 , 30(2) : 232 -236 . DOI: 10.15960/j.cnki.issn.1007-6093.2026.02.018

Abstract

A $k$-edge-coloring of a graph is an assignment of colors from a set of $k$ colors to the edges of $G$ such that adjacent edges receive distinct colors. $\chi'(G)$ denotes the smallest $k$ for which $G$ admits such a coloring. It is proved here that if a planar graph $G$ contains no $5$-fan $F_5$ as a subgraph, where $F_5$ is a graph of order $5$ with a vertex $v\in V(F_5)$ such that $d(v)=4$ and $F_5-v$ is a path, then $\chi'(G) \leq \max\{6, \Delta(G)\}$.

Key words： edge coloring; planar graph; cycle

参考文献

[1] Diestel R. 图论 [M]. 于青林, 王涛, 王光辉, 译. 北京: 高等教育出版社, 2018.
[2] Vizing V G. On an estimate of the chromatic class of a p-graph [J]. Diskret Analiz, 1964, 3: 25-30.
[3] Vizing V G. Critical graphs with a given chromatic class [J]. Diskret Analiz, 1965, 5: 9-17.
[4] Fiorini S, Wilson R J. Edge-Colourings of Graphs [M]. London: Pitman, 1977.
[5] Sanders D P, Zhao Y. Planar graphs of maximum degree seven are class 1[J]. Journal of Combinatorial Theory, Series B, 2001, 83: 202-212.
[6] Zhang L M. Every planar graph with maximum degree 7 is of class 1[J]. Graphs and Combinatorics, 2000, 16: 467-495.
[7] Wang W F, Chen Y Z. A sufficient condition for a planar graph to be class 1[J]. Theoretical Computer Science, 2007, 385: 71-77.
[8] Bu Y H, Wang W F. Some sufficient conditions for a planar graph of maximum degree six to be class 1[J]. Discrete Mathematics, 2006, 306(13): 1440-1445.
[9] Wu J L, Xue L. Edge colorings of planar graphs without 5-cycles with two chords [J]. Theoretical Computer Science, 2014, 518: 124-127.
[10] Zhang W W, Wu J L. Edge colorings of planar graphs without 6-cycles with three chords [J]. Bulletin of the Malaysian Mathematical Sciences Society, 2018, 41: 1077-1084.
[11] Zhang W W, Wu J L. Edge coloring of planar graphs without adjacent 7-cycles [J]. Theoretical Computer Science, 2018, 739: 59-64.
[12] 张文文. 两类图的边染色和无圈边染色 [D]. 济南: 山东大学, 2016.
[13] Luo R, Miao L Y, Zhao Y. The size of edge chromatic critical graphs with maximum degree 6[J]. Journal of Graph Theory, 2009, 60: 149-171.
Options
文章导航

/

〈 〉