Some results on the structure of multipoles in the study of snarks

M. A. Fiol¹ ; J. Vilaltella¹

¹Universitat Politècnica de Catalunya

The electronic journal of combinatorics, Tome 22 (2015) no. 1

Résumé

Multipoles are the pieces we obtain by cutting some edges of a cubic graph in one or more points. As a result of the cut, a multipole $M$ has vertices attached to a dangling edge with one free end, and isolated edges with two free ends. We refer to such free ends as semiedges, and to isolated edges as free edges. Every 3-edge-coloring of a multipole induces a coloring or state of its semiedges, which satisfies the Parity Lemma. Multipoles have been extensively used in the study of snarks, that is, cubic graphs which are not 3-edge-colorable. Some results on the states and structure of the so-called color complete and color closed multipoles are presented. In particular, we give lower and upper linear bounds on the minimum order of a color complete multipole, and compute its exact number of states. Given two multipoles $M_1$ and $M_2$ with the same number of semiedges, we say that $M_1$ is reducible to $M_2$ if the state set of $M_2$ is a non-empty subset of the state set of $M_1$ and $M_2$ has less vertices than $M_1$. The function $v(m)$ is defined as the maximum number of vertices of an irreducible multipole with $m$ semiedges. The exact values of $v(m)$ are only known for $m\le 5$. We prove that tree and cycle multipoles are irreducible and, as a byproduct, that $v(m)$ has a linear lower bound.

Détail

DOI : 10.37236/3629

Classification : 05C15, 05C05, 05C38
Mots-clés : cubic graph, edge-coloring, snark, multipole, parity lemma, states, color complete, color closed, separable, irreducible, cycle, linear recurrence