Decomposição de Grafos em Subgrafos Localmente Irregulares
Autores
|
6973 |
3049,3102
|
|
|
6974 |
3049,3102
|
Informações:
Publicações do PESC
Um grafo localmente irregular é um grafo no qual vértices adjacentes possuem graus distintos. Uma k-aresta coloração localmente irregular, ou kLI-coloração para simplificar, de um grafo G é uma coloração das arestas de G na qual cada classe de cor induz um subgrafo localmente irregular. Baudon, Bensmail, Przyby?o, e Wo?niak (2015) conjecturaram que se um grafo G admite uma kLI-coloração, então G admite uma 3LI-coloração. Nesta dissertação, verificamos essa conjectura para grafos potência de ciclo, para uma família de grafos cúbicos, e para algumas famílias de Snarks: Snark-Flor, Snark de Goldberg, Snark de Loupekine e Snark de Blanusa 1 e 2. Além disso, apresentamos uma condição para grafos não admitirem uma 2LI-coloração.
A locally irregular graph is a graph in which adjacent vertices have distinct degrees. A locally irregular k-edge coloring, or kLI-coloring for short, of a graph G is a coloring of the edges of G in which each color class induces a locally irregular subgraph. Baudon, Bensmail, Przyby?o, e Wo?niak (2015) conjectured that if a graph G admits a kLI-coloring, then G admits a 3LI-coloring. In this dissertation, we verify this conjecture for power of cycle graphs, for a family of cubic graphs, and for some families of Snarks: Flower Snark, Goldberg Snark, Loupekine Snark and Blanusa Snark 1 and 2. Furthermore, we present a condition for graphs not to accept a 2LI-coloring.