๐ฎ
๐ฎ
The Ethereal
Planar graphs are acyclically edge $(ฮ+ 5)$-colorable
June 27, 2023 ยท The Ethereal ยท + Add venue
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Qiaojun Shu, Guohui Lin
arXiv ID
2306.15813
Category
cs.DM: Discrete Mathematics
Cross-listed
cs.DS,
math.CO
Citations
0
Last Checked
5 months ago
Abstract
An edge coloring of a graph $G$ is to color all the edges in the graph such that adjacent edges receive different colors. It is acyclic if each cycle in the graph receives at least three colors. Fiam{ฤ}ik (1978) and Alon, Sudakov and Zaks (2001) conjectured that every simple graph with maximum degree $ฮ$ is acyclically edge $(ฮ+ 2)$-colorable -- the well-known acyclic edge coloring conjecture (AECC). Despite many major breakthroughs and minor improvements, the conjecture remains open even for planar graphs. In this paper, we prove that planar graphs are acyclically edge $(ฮ+ 5)$-colorable. Our proof has two main steps: Using discharging methods, we first show that every non-trivial planar graph must have one of the eight groups of well characterized local structures; and then acyclically edge color the graph using no more than $ฮ+ 5$ colors by an induction on the number of edges.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Discrete Mathematics
๐ฎ
๐ฎ
The Ethereal
An Introduction to Temporal Graphs: An Algorithmic Perspective
๐ฎ
๐ฎ
The Ethereal
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
๐ฎ
๐ฎ
The Ethereal
A note on the triangle inequality for the Jaccard distance
๐ฎ
๐ฎ
The Ethereal
Fast clique minor generation in Chimera qubit connectivity graphs
๐ฎ
๐ฎ
The Ethereal