To access the full text documents, please follow this link: http://hdl.handle.net/2117/27888

Some results on the structure of multipoles in the study of snarks
Fiol Mora, Miquel Àngel; Vilaltella Castanyer, Joan
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions
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 M1 and M2 with the same number of semiedges, we say that M1 is reducible to M2 if the state set of M2 is a non-empty subset of the state set of M1 and M2 has less vertices than M1. The function v(m) is defined as the maximum number of vertices of an irreducible multipole with rn semiedges. The exact values of v(m) are only known for m <= 5. We prove that tree and cycle multipoles are irreducible and, as a byproduct, that v(m) has a linear lower bound.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Graph theory
cubic graph
edge-coloring
snark
multipole
Parity Lemma
states
color complete
color closed
separable
irreducible
tree
cycle
linear recurrence
GRAPHS
Grafs, Teoria de
05C Graph theory
info:eu-repo/semantics/publishedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Barrière Figueroa, Eulalia; Comellas Padró, Francesc de Paula; Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel
Fiol Mora, Miquel Àngel; Serra Albó, Oriol
Dalfó Simó, Cristina; Van Dam, Edwin; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest; Gorissen, Bram
 

Coordination

 

Supporters