Source author record

J. Vilaltella

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

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

Multipoles are the pieces we obtain by cutting some edges of a cubic graph. As a result of the cut, a multipole $M$ 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 $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.

preprint2012arXiv

A simple and fast heuristic algorithm for edge-coloring of graphs

A simple but empirically efficient heuristic algorithm for the edge-coloring of graphs is presented. Its basic idea is the displacement of "conflicts" (repeated colors in the edges incident to a vertex) along paths of adjacent vertices whose incident edges are recolored by swapping alternating colors (that is, doing a Kempe interchange). The results of performance tests on random cubic and $Δ$ -regular graphs are presented, and a full implementation of the algorithm is given to facilitate its use and the reproducibility of results.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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