Article ID Journal Published Year Pages File Type
418998 Discrete Applied Mathematics 2015 8 Pages PDF
Abstract

An ℓℓ-facial edge coloring   of a plane graph is a coloring of the edges such that any two edges at distance at most ℓℓ on a boundary walk of any face receive distinct colors. It is conjectured that 3ℓ+1 colors suffice for an ℓℓ-facial edge coloring of any plane graph. We prove that 77 colors suffice for a 22-facial edge coloring of any plane graph and therefore we confirm the conjecture for ℓ=2ℓ=2.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , ,