Normal edge-colorings of cubic graphs

Abstract: If $G$ is a cubic graph and $f:E(G)\rightarrow \{1,...,k\}$ is a proper $k$-edge-coloring, then an edge $e=uv$ of $G$ is called poor (or rich) with respect to $f$, if $u$ and $v$ together are incident to exactly $3$ (or $5$) colors in $f$. A proper $k$-edge-coloring is called normal in $G$, if all edges of $G$ are poor or rich with respect to this coloring. The Petersen coloring of Jaeger states that all bridgeless cubic graphs admit a normal edge-coloring with at most $5$ colors. If a cubic graph contains a bridge, then it was known previously that all such cubic graphs admit a normal edge-coloring with at most $9$ colors. In this talk, we will show that all cubic graphs admit a normal edge-coloring using at most $7$ colors. This bound is best-possible, in a sense that it is tight for infinitely many cubic graphs. This is a joint work with Giuseppe Mazzuoccolo.

combinatorics

Audience: general audience

( paper | video )

Comments: talk host: Petros Petrosyan (YSU)

---

Yerevan Mathematical Colloquium

Series comments: "Yerevan Mathematical Colloquium" invites survey talks aimed at a general mathematical audience, that emphasize proof methods, relations between branches of mathematics, possible applications, and open problems.

---