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

preprint2013arXivOpen access

Abstract

Multipoles are the pieces we obtain by cutting some edges of a cubic graph. As a result of the cut, a multipole MM has dangling edges with one free end, which we call semiedges. Then, 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 M1M_1 and M2M_2 with the same number of semiedges, we say that M1M_1 is reducible to M2M_2 if the state set of M2M_2 is a non-empty subset of the state set of M1M_1 and M2M_2 has less vertices than M1M_1. The function v(m)v(m) is defined as the maximum number of vertices of an irreducible multipole with mm semiedges. The exact values of v(m)v(m) are only known for m≤5m\le 5. We prove that tree and cycle multipoles are irreducible and, as a byproduct, that v(m)v(m) has a linear lower bound.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.