Characterizations of classes of graphs by forbidden minors

Abstract

En aquest treball tractem el problema de descriure classes de grafs especificades per un menor prohibit. Concretament, presentem resultats de Wagner que caracteritzen grafs sense K5 o bé K3,3 com a menor. També donem caracteritzacions de grafs que no contenen la roda W4 amb 4 vèrtexs a la circumferència; el graf complet amb 5 vèrtexs sense una aresta; el prisme triangular; i la roda W5 amb 5 vèrtexs a la circumferència. Com a una de les eines utilitzem el teorema de Tutte de les rodes, del qual també donem una prova. La majoria dels resultats és àmpliament coneguda, però les demostracions no són disponibles fàcilment. Són complicades de trobar, incòmodes de llegir i usen terminologia obsoleta. La contribució principal d'aquest treball és recollir les demostracions en un sol lloc i presentar-les en un llenguatge modern.. Study the classical results by Wagner, Tutte and others leading to the characterizations of grahps not containing a given graph as a minor. This includes Tutte's Wheel Theorem as a preliminary. The goal is to write down complete proofs for several important forbidden minors, including K_5 and K_{3,3}.