Tese de Doutorado

A graph is locally irregular if it has no adjacent vertices with same degree. A locally irregular decomposition of a graph G is a family {G₁, . . . ,G_k} of edge-disjoint locally irregular subgraphs of G such that each edge of G belongs to exactly one of these subgraphs. If a graph G has one such decomposition, it is called decomposable and the irregular chromatic index is the smallest k such that G has a locally irregular decomposition with k members. Similarly, a regular-irregular decomposition of a graph G is a family {G₁, . . . ,G_k} of edje-disjoint subgraphs of G such that each component of any member G_i of this family is either regular or locally irregular. The regular-irregular chromatic index is defined analogously. When each regular component is isomorphic to K₂, we have a K₂-irregular decomposition and its respective K₂-irregular chromatic index. In this thesis, we discuss the most relevant results in the literature regarding these indexes, both restricted to some graph classes and for the general case. More importantly, we present contributions of our own. Amongst the less significant, there are two simple demonstrations that we did not find in the literature. The first main contribution is the proof that the irregular chromatic index of blow-ups of cycles is at most 2, and it is tight. The second is the proof that the K₂-irregular chromatic index of bipartite graphs is at most 3, which yields a reduction of almost half of the upper bound for this index on graphs in general.

Um grafo é localmente irregular se ele não tem vértices adjacentes com o mesmo grau. Uma decomposição localmente irregular de um grafo G é uma família {G₁, . . . ,G_k} de subgrafos aresta-disjuntos e localmente irregulares de G tal que cada aresta de G está em exatamente um desses subgrafos. Se um grafo G possui uma tal decomposição, ele é chamado de decomponível e o índice cromático irregular é o menor k para o qual G possui uma decomposição localmente irregular com k membros. Similarmente, uma decomposição regular-irregular de um grafo G é uma família {G₁, . . . ,G_k} de subgrafos aresta-disjuntos de G tal que cada componente de qualquer membro G_i dessa família é ou regular ou localmente irregular. O índice cromático regular-irregular é definido analogamente. Quando cada componente regular é isomorfa ao K₂, nós temos uma decomposição K₂-irregular e seu respectivo índice cromático K₂-irregular. Nesta tese, discutimos os resultados mais relevantes na literatura sobre esses índices, tanto restrito a algumas classes de grafos quanto o caso geral. Mais importante, apresentamos contribuições próprias. Dentre as menores, há duas demonstrações simples que não encontramos na literatura. A primeira contribuição principal é a prova de que o índice cromático irregular de blow-ups de ciclos é no máximo 2, e esse limitante é apertado. A segunda é a prova de que o índice cromático K₂-irregular de grafos bipartidos é no máximo 3, o que implica numa redução de quase metade do limitante para esse índice sobre grafos em geral.