Facial packing edge-coloring of plane graphs
Indexed on: 14 Jun '16Published on: 11 Jun '16Published in: Discrete Applied Mathematics
Abstract
A facial kk-packing edge-coloring of a plane graph GG is a coloring of its edges with colors 1,…,k1,…,k such that every facial trail containing two edges with the same color ii has length at least i+2i+2. The smallest integer kk such that GG admits a facial kk-packing edge-coloring is denoted by <img height="20" border="0" style="vertical-align:bottom" width="36" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0166218X1630227X-si9.gif">pf′(G). We prove that <img height="20" border="0" style="vertical-align:bottom" width="76" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0166218X1630227X-si10.gif">pf′(G)≤20 for every 3-edge-connected plane graph GG.
