Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 60 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T12:13:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-14T15:33:44Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Made available in DSpace on 2016-07-14T15:33:44Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013 / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-Lov´asz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set. / O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teorica e prática. Dado que o problema de colorir os vértices de um grafo G qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo G, a heurística b de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria c, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma, obtemos uma coloração c′ com uma cor a menos que c. Irving e Molove definiram a b-coloração de um grafo G como uma coloração onde toda classe de cor possui um vértice que é adjacente as demais classes de cor. Esses vértices são chamados b-vértices. Irving e Molove também definiram o número b-cromático como o maior inteiro k tal que G admite uma b-coloração por k cores. Eles mostraram que determinar o número b-cromático de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Irving e Molove também definiram o m-grau de um grafo, que é o maior inteiro m(G) tal que existem m(G) vértices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau é um limite superior para número b-cromático e mostraram que o mesmo é igual a m(T) ou a m(T)−1, para toda árvore T, onde o número b-cromático é igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertação, verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número b-cromático de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G é pelo menos g∗, então o número b-cromático é igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ é no máximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de Erdós-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ é 9. Caracterizamos os grafos cuja cintura é pelo menos 6 e não possuem um conjunto bom e mostramos como b-colori-los de forma ótima. Além disso, mostramos como bicolorir, também de forma ótima, os grafos cuja cintura é pelo menos 7 e não possuem conjunto bom.

LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 59 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza- Ceará, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T18:53:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T19:18:47Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Made available in DSpace on 2016-06-13T19:18:47Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013 / O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teorica e prática. Dado que o problema de colorir os vértices de um grafo G qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo G, a heurística b de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria c, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma, obtemos uma coloração c′ com uma cor a menos que c. Irving e Molove definiram a b-coloração de um grafo G como uma coloração onde toda classe de cor possui um vértice que é adjacente as demais classes de cor. Esses vértices são chamados b-vértices. Irving e Molove também definiram o número b-cromático como o maior inteiro k tal que G admite uma b-coloração por k cores. Eles mostraram que determinar o número b-cromático de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Irving e Molove também definiram o m-grau de um grafo, que é o maior inteiro m(G) tal que existem m(G) vértices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau é um limite superior para número b-cromático e mostraram que o mesmo é igual a m(T) ou a m(T)−1, para toda árvore T, onde o número b-cromático é igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertação, verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número b-cromático de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G é pelo menos g∗, então o número b-cromático é igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ é no máximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de Erdós-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ é 9. Caracterizamos os grafos cuja cintura é pelo menos 6 e não possuem um conjunto bom e mostramos como b-colori-los de forma ótima. Além disso, mostramos como bicolorir, também de forma ótima, os grafos cuja cintura é pelo menos 7 e não possuem conjunto bom. / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-Lov´asz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set.

Covering arrays for words of length (Formula presented.) over a (Formula presented.) -letter alphabet are (Formula presented.) arrays with entries from the alphabet so that for each choice of (Formula presented.) columns, each of the (Formula presented.) (Formula presented.) -letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case known as partitioning hash families, words are equivalent if they induce the same partition of a (Formula presented.) element set. In the second case, words of the same weight are equivalent. In both cases, we produce logarithmic upper bounds on the minimum size (Formula presented.) of a covering array. Definitive results for (Formula presented.), as well as general results, are provided.

We investigate the ultraconnectivity condition on graphs, and provide further connections between critical and ultraconnected graphs in the positive definite partial matrix completion problem. We completely characterize when the join of graphs is ultraconnected, and prove that ultraconnectivity is preserved by Cartesian products. We completely characterize when adding a vertex to an ultraconnected graph preserves ultraconnectivity. We also derive bounds on the number of vertices which guarantee ultraconnectivity of certain classes of regular graphs. We give results from our exhaustive enumeration of ultraconnected graphs up to 11 vertices. Using techniques involving the Lovász theta parameter for graphs, we prove certain classes of graphs are critical (and hence ultraconnected) in the positive definite partial matrix completion problem.

In the 1970’s, L. Lovász proved that two graphs G and H are isomorphic if and only if for every graph X , the number of homomorphisms from X → G equals the number of homomorphisms from X → H . He used this result to deduce cancellation properties of the direct product of graphs. We develop a result analogous to Lovász’s theorem, but in the class of graphs without loops and with weak homomorphisms. We apply it prove a general cancellation property for the strong product of graphs.

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs. Cette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité. Le deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: Si G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G. La meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G) <= 3/2 n pour une classe de graphes la plus large possible. Un autre résultat associé à ce problème apporte la preuve de la conjecture pour une classe particulière de graphes: Soit G un graphe simple avec alpha(G) = 2. Si G a une arête dominante uv telle que G \ {u,v} est de diamètre 3, alors ecc(G) <= n. Le troisième problème étudie le jeu de policier et voleur sur un graphe. Presque toutes les études concernent les graphes statiques, et nous souhaitons explorer ce jeu sur les graphes dynamiques, dont les ensembles d’arêtes changent au cours du temps. Nowakowski et Winkler caractérisent les graphes statiques pour lesquels un unique policier peut toujours attraper le voleur, appellés cop-win, à l’aide d’une relation <= définie sur les sommets de ce graphe: Un graphe G est cop-win si et seulement si la relation <= définie sur ses sommets est triviale. Nous adaptons ce théorème aux graphes dynamiques. Notre démarche nous mène à une relation nous permettant de présenter une caractérisation des graphes dynamiques cop-win. Nous donnons ensuite des résultats plus spécifiques aux graphes périodiques. Nous indiquons aussi comment généraliser nos résultats pour k policiers et l voleurs en réduisant ce cas à celui d’un policier unique et un voleur unique. Un algorithme pour décider si, sur un graphe périodique donné, k policiers peuvent capturer l voleurs découle de notre caractérisation. / This thesis represents in three articles my eclectic interest for graph theory. The first problem is the conjecture of Erdos-Faber-Lovász: If k complete graphs, each having k vertices, have the property that every pair of distinct complete graphs have at most one vertex in common, then the vertices of the resulting graph can be properly coloured by using k colours. This conjecture is notable in that only a handful of classes of EFL graphs are proved to satisfy the conjecture. We prove that the Erdos-Faber-Lovász Conjecture holds for a new class of graphs, and we do so by an inductive argument. Furthermore, graphs in this class have no restrictions on the number of complete graphs to which a vertex belongs or on the number of vertices of a certain type that a complete graph must contain. The second problem addresses a conjecture concerning the covering of the edges of a graph: The minimal number of cliques necessary to cover all the edges of a simple graph G is denoted by ecc(G). If alpha(G) = 2, then ecc(G) <= n. The best known bound satisfied by ecc(G) for all the graphs with independence number two is the minimum of n + delta(G) and 2n − omega(square root (n log n)), where delta(G) is the smallest number of neighbours of a vertex in G. In this type of graph, all the vertices at distance two from a given vertex form a clique. Our approach is to extend all of these n cliques in order to cover the maximum possible number of edges. Unfortunately, there are graphs for which it’s impossible to cover all the edges with this method. However, we are able to use this approach to prove a bound of ecc(G) <= 3/2n for some newly studied infinite families of graphs. The third problem addresses the game of Cops and Robbers on a graph. Almost all the articles concern static graphs, and we would like to explore this game on dynamic graphs, the edge sets of which change as a function of time. Nowakowski and Winkler characterize static graphs for which a cop can always catch the robber, called cop-win graphs, by means of a relation <= defined on the vertices of such graphs: A graph G is cop-win if and only if the relation <= defined on its vertices is trivial. We adapt this theorem to dynamic graphs. Our approach leads to a relation, that allows us to present a characterization of cop-win dynamic graphs. We will then give more specific results for periodic graphs, and we will also indicate how to generalize our results to k cops and l robbers by reducing this case to one with a single cop and a single robber. An algorithm to decide whether on a given periodic graph k cops can catch l robbers follows from our characterization.