Número cromático acíclico das arestas de um grafo com girth grande
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Acyclic chromatic number of the edges of a graph with large girth
Primeiro orientador
Membros da banca
Adrian Pablo Hinojosa Luna
Aldo Procacci
Mauricio de Lemos Rodrigues Collares Neto
Rodrigo Bissacot Proença
Paula Mendes Soares Fialho
Aldo Procacci
Mauricio de Lemos Rodrigues Collares Neto
Rodrigo Bissacot Proença
Paula Mendes Soares Fialho
Resumo
Este trabalho busca aprimorar o estudo da coloração acíclica das arestas de um grafo $G=(V,E)$, com cintura mínima $g$, com base em algoritmos aleatórios do tipo Moser-Tardos. Seja $\Delta$ o grau máximo de um vértice $v$ de um grafo $G$, o número cromático acíclico das arestas de $G$, representado por $a'(G)$, é o menor número de cores necessário para colorir propriamente suas arestas de modo que nenhum de seus ciclos tenham apenas duas cores. Foi conjecturado por Fiam$\check{c}$ik \cite{fiamcik} e depois por \cite{alonetal2} que $a'(G)\leq \Delta +2$. Ao longo do tempo, pesquisadores da área têm buscado uma melhor cota superior para $a'(G)$. Atualmente, o melhor resultado se dá por Fialho, Lima e Procacci \cite{fialho1}, responsáveis por estabelecer que $a'(G)\leq 3.569(\Delta -1)$. Neste trabalho, para qualquer $\varepsilon>0$, determinamos explicitamente uma cintura $g(\varepsilon,m)$, onde $m$ é o número de arestas, tal que se $g\geq g(\varepsilon,m)$, então, $G$ admite uma coloração acíclica das arestas com $(1 + \varepsilon)\Delta$ cores. Além disso, o Teorema Principal apresentado a seguir na Introdução permite, fixando o número de arestas $m$, a veracidade da conjectura de Fiam$\check{c}$ik em que $g\geq g_{\Delta,m}$. Por exemplo, fixando $m=5\times10^5$ e para $g\geq35$ a conjectura é válida.
Abstract
This work aims to enrich the study of acyclic edge coloring of a graph G = (V,E), with a minimum girth g, based on Moser-Tardos type random algorithms. Let ∆ be the maximum degree of a vertex v in a graph G. The acyclic chromatic index of G, denoted by a ′(G), is the smallest number of colors required to properly color its edges such that none of its cycles are bichromatic. It was conjectured by Fiamˇcik [14] and after for [2] that a ′ (G) ≤ ∆ + 2. Over time, researchers have sought a better upper bound for a ′ (G). Currently, the best result is by Fialho, Lima, and Procacci [13], who established that a ′ (G) ≤ 3.569(∆−1). In this work, for any ε > 0, we explicitly determine a girth g(ε,m), where m is the number of edges, such that if g ≥ g(ε,m), then G admits an acyclic edge coloring with (1 + ε)∆ colors. Moreover, the Main Theorem presented later in the Introduction, demonstrates that by fixing the number of edges m, Fiamˇcik’s conjecture holds for g ≥ g∆,m. For example, by fixing m = 5 × 105 and for g ≥ 35, the conjecture is valid.
Assunto
Estatística – Teses, Análise combinatória – Teses, Teoria dos grafos – Teses, Grafos aleatórios – Teses
Palavras-chave
coloração acíclica de arestas, cintura, número cromático, algoritmos aleatórios