[pt] Uma coloração de arestas é a atribuição de cores às arestas de um grafo, de modo que arestas adjacentes não recebam a mesma cor. O menor inteiro positivo para o qual um grafo admite uma coloração de arestas é dito seu índice cromático. Fizemos revisão bibliográfica dos principais resultados conhecidos nessa área. Uma coloração total, por sua vez, é a aplicação de cores aos vértices e arestas de um grafo de modo que elementos adjacentes ou incidentes recebam cores distintas. O número cromático total de um grafo é o menor inteiro positivo para o qual o grafo possui coloração total. Dada uma coloração total, se a diferença entre as cardinalidades de quaisquer duas classes de cor for no máximo um, então dizemos que a coloração é equilibrada e o menor número inteiro positivo que satisfaz essa condição é dito o número cromático total equilibrado do grafo. Para tal valor, Wang (2002) conjecturou um limite superior. Um grafo multipartido completo balanceado é aquele em que o conjunto de vértices pode ser particionado em conjuntos independentes com a mesma quantidade de vértices, sendo adjacentes quaisquer dois vértices de diferentes partes da partição. Determinamos o número cromático total equilibrado dos grafos multipartidos completos balanceados, contribuindo, desta forma, com novos resultados na área de coloração de grafos. / [en] An edge coloring is the assignment of colors to the edges of a graph, so that adjacent edges do not receive the same color. The smallest positive integer for which a graph admits an edge coloring is said to be its chromatic index. We did a literature review of the main known results of this area. A total coloring, in turn, is the application of colors to the vertices and edges of a graph so that adjacent or incident elements receive distinct colors. The total chromatic number of a graph is the least positive integer for which the graph has a total coloring.Given a total coloring, if the difference between the cardinality of any two color classes is at most one, then we say that the coloring is equitable and the smallest positive integer that satisfies this condition is said to be the graph s equitable total chromatic number. For such value, Wang (2002) conjectured an upper bound. A complete multipartite balanced graph is the one in which the set of vertices can be partitioned into independent sets with the same quantity of vertices, being adjacent any two vertices of different parts of the partition. We determine the equitable total chromatic number of complete multipartite graphs, contributing, therefore, with new results in the area of graph coloring.

Abstract: This thesis studies five kinds of graph colorings: the circular coloring, the total coloring, the (d; 1)-total labeling, the circular (r; 1)-total labeling, and the acyclic list coloring. We give upper bounds on the circular chromatic number of graphs with small maximum average degree, mad for short. It is proved that if mad(G)<22=9 then G has a 11=4-circular coloring, if mad(G) < 5=2 then G has a 14=5-circular coloring. A conjecture by Behzad and Vizing implies that £G+2 colors are always sufficient for a total coloring of graphs with maximum degree £G. The only open case for planar graphs is for £G = 6. Let G be a planar in which no vertex is contained in cycles of all lengths between 3 and 8. If £G(G) = 6, then G is total 8-colorable. If £G(G) = 8, then G is total 9-colorable. Havet and Yu [23] conjectured that every subcubic graph G ̸=K4 has (2; 1)-total number at most 5. We confirm the conjecture for graphs with maximum average degree less than 7=3 and for flower snarks. We introduce the circular (r; 1)-total labeling. As a relaxation of the aforementioned conjecture, we conjecture that every subcubic graph has circular (2; 1)-total number at most 7. We confirm the conjecture for graphs with maximum average degree less than 5=2. We prove that every planar graph with no cycles of lengths 4, 7 and 8 is acyclically 4-choosable. Combined with recent results, this implies that every planar graph with no cycles of length 4;k; l with 5 6 k < l 6 8 is acyclically 4-choosable.

Un k-coloriage total d'un graphe G est un coloriage de V(G)cup E(G) utilisant (1,2,…,k) couleurs tel qu'aucune paire d'éléments adjacents ou incidents ne reçoivent la même couleur. Le nombre chromatique total chi''(G) est le plus petit entier k tel que G admette un k-coloriage total. Dans le chapitre 2, nous étudions la coloration totale de graphe planaires et obtenons 3 résultats : (1) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si toutes les paires de 6-cycles cordaux ne sont pas adjacentes dans G, alors chi''(G)=Delta+1. (2) Soit G un graphe planaire avec pour degré maximum Deltageq8. Si tout 7-cycle de G contient au plus deux cordes, alors chi''(G)=Delta+1. (3) Soit G un graphe planaire sans 5-cycles cordaux qui s'intersectent, c'est à dire tel que tout sommet ne soit incident qu'à au plus un seul 5-cycle cordal. Si Deltageq7, alors chi''(G)=Delta+1.Une relation L est appelé assignation pour un graphe G s'il met en relation chaque x à une liste de couleur. S'il est possible de colorier G tel que la couleur de chaque x soit présente dans la liste qu'il lui a été assignée, et qu'aucune paire de sommets adjacents n'aient la même couleur, alors on dit que G est L-coloriable. Un graphe G est k-selectionable si G est L-coloriable pour toute assignation L de G qui satisfait |L(v)geq k| pour tout x. Nous démontrons que si chaque 5-cycle de G n'est pas simultanément adjacent à des 3-cycles et des 4-cycles, alors G est 4-sélectionable. Dans le chapitre 3, nous prouvons que si aucun des 5-cycles de G n'est adjacent à un 4-cycles, alors chi'_l(G)=Delta et chi''_l(G)=Delta+1 si Delta(G)geq8, et chi'_l(G)leqDelta+1 et chi''_l(G)leqDelta+2 si Delta(G)geq6.Dans le chapitre 4, nous allons fournir une définition du coloriage total somme-des-voisins-distinguant, et passer en revue les progrgrave{e}s et conjecture concernant ce type de coloriage. Soit f(v) la somme des couleurs d'un sommet v et des toutes les arrêtes incidentes à v. Un k-coloriage total somme-des-voisins-distinguant de G est un k coloriage total de G tel que pour chaque arrête uvin E(G), f(u)eq f(v). Le plus petit k tel qu'on ai un tel coloriage sur G est appelé le nombre chromatique total somme-des-voisins-distinguant, noté chi''_{sum} (G). Nous avons démontré que si un graphe G avec degré maximum Delta(G) peut être embedded dans une surface Sigma de caractéristique eulérienne chi(Sigma)geq0, alors chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Une forêt linéaire est un graphe pour lequel chaque composante connexe est une chemin. L'arboricité linéaire la(G) d'un graphe G tel que définie est le nombre minimum de forêts linéaires dans G, dont l'union est égale à V(G). Dans le chapitre 5, nous prouvons que si G est une graphe planaire tel que tout 7-cycle de G contienne au plus deux cordes, alors G est linéairementleft lceil frac{Delta+1}{2}ightceil-sélectionable si Delta(G)geq6, et G est linéairement left lceil frac{Delta}{2}ightceil-sélectionable si Delta(G)geq 11. / A k-total-coloring of a graph G is a coloring of V(G)cup E(G) using (1,2,…,k) colors such that no two adjacent or incident elements receive the same color．The total chromatic number chi''(G) is the smallest integer k such that G has a k-total-coloring. In chapter 2, we study total coloring of planar graphs and obtain three results: (1) Let G be a planar graph with maximum degree Deltageq8. If every two chordal 6-cycles are not adjacent in G, then chi''(G)=Delta+1. (2) Let G be a planar graph G with maximum degree Deltageq8. If any 7-cycle of G contains at most two chords, then chi''(G)=Delta+1. (3) Let G be a planar graph without intersecting chordal 5-cycles, that is, every vertex is incident with at most one chordal 5-cycle. If Deltageq7, then chi''(G)=Delta+1.A mapping L is said to be an assignment for a graph G if it assigns a list L(x) of colors to each xin V(G)cup E(G). If it is possible to color G so that every vertex gets a color from its list and no two adjacent vertices receive the same color, then we say that G is L-colorable. A graph G is k-choosable if G is an L-colorable for any assignment L for G satisfying |L(x)|geq k for every vertex xin V(G)cup E(G). We prove that if every 5-cycle of G is not simultaneously adjacent to 3-cycles and 4-cycles, then G is 4-choosable. In chapter 3, if every 5-cycles of G is not adjacent to 4-cycles, we prove that chi'_l(G)=Delta, chi''_l(G)=Delta+1 if Delta(G)geq8, and chi'_l(G)leqDelta+1, chi''_l(G)leqDelta+2 if Delta(G)geq6.In chapter 4, we will give the definition of neighbor sum distinguishing total coloring. Let f(v) denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total k-neighbor sum distinguishing-coloring of G is a total k-coloring of G such that for each edge uvin E(G), f(u)eq f(v). The smallestnumber k is called the neighbor sum distinguishing total chromatic number, denoted by chi''_{sum} (G). Pilsniak and Wozniak conjectured that for any graph G with maximum degree Delta(G) holds that chi''_{sum} (G)leqDelta(G)+3. We prove for a graph G with maximum degree Delta(G) which can be embedded in a surface Sigma of Euler characteristic chi(Sigma)geq0, then chi_{sum}^{''}(G)leq max{Delta(G)+2, 16}.Lastly, we study the linear L-choosable arboricity of graph. A linear forest is a graph in which each component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests in G, whose union is the set of all edges of G. A list assignment L to the edges of G is the assignment of a set L(e)subseteq N of colors to every edge e of G, where N is the set of positive integers. If G has a coloring varphi (e) such that varphi (e)in L(e) for every edge e and (V(G),varphi^{-1}(i)) is a linear forest for any iin C_{varphi}, where C_{varphi }=left { varphi (e)|ein E(G)ight }, then we say that G is linear L-colorable and varphi is a linear L-coloring of G. We say that G is linear k-choosable if it is linear L-colorable for every list assignment L satisfying |L(e)| geq k for all edges e. The list linear arboricity la_{list}(G) of a graph G is the minimum number k for which G is linear k-list colorable. It is obvious that la(G)leq la_{list}(G). In chapter 5, we prove that if G is a planar graph such that every 7-cycle of G contains at most two chords, then G is linear left lceil frac{Delta+1}{2}ightceil-choosable if Delta(G)geq6, and G is linear left lceil frac{Delta}{2}ightceil-choosable if Delta(G)geq 11.