A Tutte trail T of a graph G is a trail such that every component of GnV (T) has at most three edges connecting it to T. In 1992, Bill Jackson conjectured that every 2-edge-connected graph G has a Tutte closed trail. In this thesis, we show that Jackson's conjecture is true when G is embedded on the plane and the projective plane. We also give some partial results when G is embedded on the torus.

Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.

Made available in DSpace on 2014-06-12T18:28:51Z (GMT). No. of bitstreams: 2 arquivo4264_1.pdf: 8529909 bytes, checksum: 0a958aa0c57b9a6b54d2a7542dbf9476 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Um blink é um grafo plano onde cada aresta ou é vermelha ou é verde. Um espaço 3D ou, simplesmente, um espaço é uma variedade 3-dimensional conexa, fechada e orientada. Neste trabalho exploramos pela primeira vez em maiores detalhes o fato de que todo blink induz um espaço e todo espaço é induzido por algum blink (na verdade por infinitos blinks). Qual o espaço de um triângulo verde? E de um quadrado vermelho? São iguais? Estas perguntas foram condensadas numa pergunta cuja busca pela resposta guiou em grande parte o trabalho desenvolvido: quais são todos os espaços induzidos por blinks pequenos (poucas arestas)? Nesta busca lançamos mão de um conjunto de ferramentas conhecidas: os blackboard framed links (BFL), os grupos de homologia, o invariante quântico de Witten-Reshetikhin-Turaev, as 3-gems e sua teoria de simplificação. Combinamos a estas ferramentas uma teoria nova de decomposição/composição de blinks e, com isso, conseguimos identificar todos os espaços induzidos por blinks de até 9 arestas (ou BFLs de até 9 cruzamentos). Além disso, o nosso esforço resultou também num programa interativo de computador chamado BLINK. Esperamos que ele se mostre útil no estudo de espaços e, em particular, na descoberta de novos invariantes que complementem o invariante quântico resolvendo as duas incertezas deixadas em aberto neste trabalho