Contribucions a la teoria de l'aresta-acoloriment de grafs : snarks i multipols

A graph where every vertex has three neighboring vertices is a cubic graph. An edge-coloring is an assignment of colors to the edges of a graph in such a way that the edges incident to a vertex have no repeated colors. An edge-coloring is optimal if it uses the minimum possible number of colors. Vizing's Theorem implies that an optimal edge-coloring of a cubic graph requires three or four colors. If three colors are enough, we call the edge-coloring a Tait-coloring. If four colors are needed, we call the graph a snark. Holyer proved that deciding wether a cubic graph is Tait-colorable is an NP-complete problem, therefore it is widely believed that it is a very difficult or intractable problem in the general case. Nevertheless, theory does not forbid efficient solutions in specific cases: this is called "breaking intractability". We describe an heuristic algorithm called CVD, for "Conflicting Vertex Displacement", which has a good empirical performance in random regular graphs. Also it allows us to check a conjecture by Biggs on "odd graphs" in instances with milions of vertices and edges, using moderately powerful computers. Snarks are relevant in graph theory: they appear often as minimal counterexamples of important conjectures, such as the Cycle Double Cover Conjecture (every bridgeless graph has a family of cycles such that every edge belongs to exactly two cycles of the family). In the analysis and synthesis of snarks, multipoles, "pieces" of cubic graphs with free ends that can be joined to each other, are often used. In a Tait-colored multipole, the number of equally colored free ends for each color and the total number of free ends have the same parity (the number of vertices of the multipole has this same parity, too). This result, known as the Parity Lemma, allows the interpretation of multipoles as logic gates and cubic graphs as logic circuits. This gives a very general way to construct snarks, based on logic circuits with no valid Boolean assignment, and allows us to relate the Tait-coloring of cubic graphs to integer factorization. In particular, we can construct snarks from prime numbers. A state of a multipole is the restriction of a Tait-coloring of the multipole to its free ends. If the set of states of a multipole is a non-empty subset of the set of states of another multipole with a larger number of vertices, we call the smaller multipole a reduction of the larger one. An irreducible multipole is a multipole with no reduction (an obvious example is a minimal multipole, that is, with no vertices or with a single vertex). The maximum number of vertices of an irreducible multipole as a function of its number (m) of free ends is denoted by v(m). Its behavior is well-known only for m

Un graf on cada vèrtex té tres vèrtexs adjacents és un graf cúbic. Un aresta-acoloriment és una assignació de colors a les arestes d'un graf de tal manera que no es repeteixin colors en les arestes incidents a un mateix vèrtex. Un aresta-acoloriment és òptim si utilitza el mínim nombre possible de colors. El Teorema de Vizing implica que un aresta-acolorament òptim d'un graf cúbic requereix tres o quatre colors. Si tres colors són suficients, de l'aresta-acoloriment en diem Tait-acoloriment. Si fan falta quatre colors, diem que el graf és un snark. Holyer va demostrar que determinar si un graf cúbic és Tait-acolorible és un problema NP-complet, i per tant se suposa àmpliament que és un problema molt difícil o intractable en el cas general. Tanmateix, la teoria no prohibeix que es puguin resoldre eficientment casos concrets: és el que s'anomena "ruptura de la intractabilitat". Descrivim un algorisme heurístic anomenat DVC, per "Desplaçament de Vèrtexs Conflictius", que té un bon rendiment empíric en grafs regulars aleatoris. També ens permet comprovar una conjectura de Biggs sobre els "odd graphs" en instàncies de milions de vèrtexs i arestes, utilitzant ordinadors de potència moderada. Els snarks són rellevants en la teoria de grafs: sovint apareixen com a contraexemples minimals de conjectures importants, com per exemple la Conjectura del Recobriment Doble per Cicles (tot graf sense ponts té una família de cicles tal que cada aresta pertany exactament a dos dels cicles). En l'anàlisi i síntesi d'snarks se solen utilitzar multipols, que són "peces" de grafs cúbics amb extrems lliures que es poden unir entre ells. En un multipol Tait-acolorit, el nombre d'extrems lliures de cada color té la mateixa paritat que el nombre total d'extrems lliures (i que el nombre de vèrtexs del multipol). Aquest resultat, conegut com el Lema de Paritat, permet interpretar els multipols com a portes lògiques i els grafs cúbics com a circuits lògics. Això proporciona una manera molt general de construir snarks, en base a circuits lògics sense cap assignació booleana vàlida, i també permet relacionar l'aresta-acoloriment de grafs amb la factorització de nombres enters. En particular, permet construir snarks a partir de nombres primers. Un estat d'un multipol és la restricció d'un Tait-acoloriment del multipol als seus extrems lliures. Si el conjunt d'estats d'un multipol és un subconjunt no buit del conjunt d'estats d'un altre multipol amb un nombre de vèrtexs més gran, diem que n'és una reducció. Un multipol irreductible és un multipol sense cap reducció (un exemple obvi és un multipol minimal, és a dir sense vèrtexs o amb un sol vèrtex). El màxim nombre de vèrtexs d'un multipol irreductible en termes del seu nombre d'extrems lliures és una funció, representada per v(m), el comportament de la qual només es coneix exactament per m