Suppose $G$ is a graph and $e=ab$ is an edge of $G$. For a positive integer $k$, the $G$-necklace of length $k$ (with respect to edge $e$), denoted by $N_k(G)$, is the graph constructed as follows: Take the vertex disjoint union of $k$ copies of $G$, say $Q_1 cup Q_2 cup cdots cup Q_k$, where each $Q_i$ is a copy of $G$, with $e_i=a_ib_i$ be the copy of $e=a b$ in $Q_i$. Add a vertex $u$, delete the edges $e_i$ for $i=1, 2, cdots, k$ and add edges: $ua_1, b_1a_2, b_2a_3, cdots, b_{k-1}a_k, b_ku$. This thesis determines the circular chromatic indexes of $G$-necklaces for $G = K_{2n}$ and $G= K_{m, m}$.(¨£¹q¤l½×¤å²Ä¤»­¶)

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

No description available.

A star edge coloring is any edge coloring which is both proper and contains no cycles or path of length four which are bicolored, and the star chromatic index of a graph is the smallest number of colors for which that graph can be star edge colored. Star edge coloring is a relatively new field in graph theory, and very little is known regarding upper bounds of the star chromatic index of most graph types, one of these families being multipartite graphs. We investigate a method for obtaining upper bounds on the star chromatic index of complete multipartite graphs. The basic idea is to decompose such graphs into smaller complete bipartite graphs and applying known upper bounds for such graphs.This method has also been implemented and we present a hypothesis based on simulations.

[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.

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:41Z No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:55Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:27:03Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Made available in DSpace on 2017-10-09T16:27:11Z (GMT). No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) Previous issue date: 2017-05-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Let G = (V, E) be a simple and undirected graph. An edge-coloring is an assignment of colors to the edges of the graph such that any two adjacent edges receive different colors. The chromatic index of a graph G is the smallest number of colors such that G has an edge-coloring. Clearly, a lower bound for the chromatic index is the degree of the vertex of higher degree, denoted by ?(G). In 1964, Vizing proved that chromatic index is ?(G) or ?(G) + 1. The Classification Problem is to determine if the chromatic index is ?(G) (Class 1 ) or if it is ?(G) + 1 (Class 2 ). Let n be number of vertices of a graph G and let m be its number of edges. We say G is overfull if m > (n-1) 2 ?(G). Every overfull graph is Class 2. A graph is subgraph-overfull if it has a subgraph with same maximum degree and it is overfull. It is well-known that every overfull and subgraph-overfull graph is Class 2. The Overfull Conjecture asserts that every graph with ?(G) > n 3 is Class 2 if and only if it is subgraph-overfull. In this work we prove the Overfull Conjecture to a particular class of graphs, known as split-comparability graphs. The Overfull Conjecture was open to this class. / Dado um grafo simples e não direcionado G = (V, E), uma coloração de arestas é uma função que atribui cores às arestas do grafo tal que todas as arestas que incidem em um mesmo vértice têm cores distintas. O índice cromático é o número mínimo de cores para obter uma coloração própria das arestas de um grafo. Um limite inferior para o índice cromático é, claramente, o grau do vértice de maior grau, denotado por ?(G). Em 1964, Vizing provou que o índice cromático ou é ?(G) ou ?(G) + 1, surgindo assim o Problema da Classificação, que consiste em determinar se o índice cromático é ?(G) (Classe 1 ) ou ?(G) + 1 (Classe 2 ). Seja n o número de vértices de um grafo G e m seu número de arestas. Dizemos que um grafo é sobrecarregado se m > (n-1) 2 ?(G). Um grafo é subgrafo-sobrecarregado se tem um subgrafo de mesmo grau máximo que é sobrecarregado. É sabido que se um grafo é sobrecarregado ou subgrafo-sobrecarregado ele é necessariamente Classe 2. A Conjectura Overfull é uma famosa conjectura de coloração de arestas e diz que um grafo com ?(G) > n 3 é Classe 2 se e somente se é subgrafo-sobrecarregado. Neste trabalho provamos a Conjectura Overfull para uma classe de grafos, a classe dos grafos split-comparabilidade. Até este momento a Conjectura Overfull estava aberta para esta classe.

An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(G)" />. This paper proves an upper bound of the star chromatic index of bipartite graphs in terms of the maximum degree; the maximum degree of G is the largest number of edges incident to a single vertex in G. For bipartite graphs Bk with maximum degree <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?k%5Cgeq1" />, the star chromatic index is proven to satisfy<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%20%5Cchi'_%7Bst%7D(B_k)%20%5Cleq%20k%5E2%20-%20k%20+%201" />. For bipartite graphs <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B_%7Bk,n%7D" />, where all vertices in one part have degree n, and all vertices in the other part have degree k, it is proven that the star chromatic index satisfies <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(Bk,n)%20%5Cleq%20k%5E2%20-2k%20+%20n%20+%201,%20k%20%5Cgeq%20n%20%3E%201" />. We also prove an upper bound for a special case of multipartite graphs, namely <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?K_%7Bn,1,1,%5Cdots,1%7D" /> with m parts of size one. The star chromatic index of such a graph satisfies<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(K_%7Bn,1,1,%5Cdots,1%7D)%20%5Cleq%2015%5Clceil%5Cfrac%7Bn%7D%7B8%7D%5Crceil%5Ccdot%5Clceil%5Cfrac%7Bm%7D%7B8%7D%5Crceil%20+%20%5Cfrac%7B1%7D%7B2%7Dm(m-1),%5C,m%20%5Cgeq%205" />. For complete multipartite graphs where m &lt; 5, we prove lower upper bounds than the one above.