Operations Research Transactions ›› 2026, Vol. 30 ›› Issue (2): 232-236.doi: 10.15960/j.cnki.issn.1007-6093.2026.02.018

Previous Articles     Next Articles

Edge colorings of planar graphs without 5-fans

XUE Ling1, WU Jianliang2,†   

  1. 1 Department of Information Engineering, Taishan Polytechnic, Taian 271000, Shandong, China;
    2 School of Mathematics, Shandong University, Jinan 250100, Shandong, China
  • Received:2024-05-06 Published:2026-06-12

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

CLC Number: