Facial packing edge-coloring of plane graphs

Research paper by Július Czap, Stanislav Jendrol’

Indexed on: 14 Jun '16Published on: 11 Jun '16Published in: Discrete Applied Mathematics


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.

Figure 10.1016/j.dam.2016.05.010.0.jpg