Cette thèse concerne quatre problèmes de coloration de graphes NPdifficiles, à savoir le problème de coloration (GCP), le problème de coloration équitable (ECP), le problème de coloration des sommets pondérés et le problème de sous-graphe critique (k-VCS). Ces problèmes sont largement étudiés dans la littérature, non seulement pour leur difficulté théorique, mais aussi pour leurs applications réelles dans de nombreux domaines. Étant donné qu'ils appartiennent à la classe de problèmes NP-difficiles, il est difficile de les résoudre dans le cas général de manière exacte. Pour cette raison, cette thèse est consacrée au développement d'approches heuristiques pour aborder ces problèmes complexes. Plus précisément, nous développons un algorithme mémétique de réduction (RMA) pour la coloration des graphes, un algorithme de recherche réalisable et irréalisable (FISA) pour la coloration équitable et un réalisable et irréalisable (AFISA) pour le problème de coloration des sommets pondérés et un algorithme de suppression basé sur le retour en arrière (IBR) pour le problème k-VCS. Tous les algorithmes ont été expérimentalement évalués et comparés aux méthodes de l'état de l'art. / This thesis concerns four NP-hard graph coloring problems, namely, graph coloring (GCP), equitable coloring (ECP), weighted vertex coloring (WVCP) and k-vertex-critical subgraphs (k-VCS). These problems are extensively studied in the literature not only for their theoretical intractability, but also for their real-world applications in many domains. Given that they belong to the class of NP-hard problems, it is computationally difficult to solve them exactly in the general case. For this reason, this thesis is devoted to developing effective heuristic approaches to tackle these challenging problems. We develop a reduction memetic algorithm (RMA) for the graph coloring problem, a feasible and infeasible search algorithm (FISA) for the equitable coloring problem, an adaptive feasible and infeasible search algorithm (AFISA) for the weighted vertex coloring problem and an iterated backtrack-based removal (IBR) algorithm for the k-VCS problem. All these algorithms were experimentally evaluated and compared with state-of-the-art methods.

Le problème de coloration de graphe est un problème NP-complet particulièrement étudié, qui permet de modéliser de problèmes dans des domaines variés. Dans cette thèse, de nouveaux algorithmes exacts basés sur une étude de la structure du graphe sont proposés. Ce travail s'appuie sur l'algorithme « Total solutions Exact graph Coloring » (TexaCol) qui construit toutes les solutions en exploitant l'ensemble des cliques d'un graphe. Deux algorithmes exacts, « Partial best solutions Exact graph Coloring » (PexaCol) et « All best solutions Exact graph Coloring » (AexaCol), sont présentés ici pour construire certaines solutions optimales ou toutes les meilleures solutions. Ces deux algorithmes utilisent la méthode de backtracking, dans laquelle ils ne choisissent que les sous-ensembles de meilleurs solutions pour continuer la coloration. L’analyse de résultat montre que PexaCol et AexaCol sont capables de traiter des graphes plus grands que TexaCol. Mais surtout, AexaCol trouve toutes les meilleures solutions significativement plus vite que TexaCol ainsi que le solveur Gurobi, qui sont utilisés comme référence.La téléphonie mobile est un domaine en plein essor qui peut s'appuyer sur une modélisation à base de graphes. Actuellement, les techniques de type « Device-to-Device » (D2D) prennent une place importante dans les réseaux mobiles. L’allocation de ressource constitue l'un des principaux problèmes en matière de performance. Pour assigner efficacement une ressource radio à une paire D2D dans le système Long-Term Evolution (LTE), un schéma systématique d'allocation de ressources est proposé dans cette thèse. Il est basé sur une clusturisation des liens D2D, et permet de prendre en compte à la fois l'allocation inter-cluster et intra-cluster des ressources. En déterminant les zones d'interférence, le problème d'allocation des ressources inter-cluster est formulé comme un problème de coloration de graphe dynamique. Un algorithme de coloration de graphe dynamique est ainsi proposé, basé sur PexaCol. Cet algorithme peut assigner les ressources radio aux clusters qui sont générés ou supprimés dynamiquement. L’analyse numérique montre que cet algorithme assure une bonne performance en termes d'utilisation des ressources, de temps d’exécution et d'adaptabilité. Concernant le problème d’allocation de ressources inter-cluster, une méthode fondée sur la topologie est proposée, intégrant naturellement l'allocation de puissance et l’allocation de Resource Block (RB). Pour simplifier ce problème d'allocation de ressources, la meilleure topologie est choisie à chaque étape, celle qui permet d'obtenir le meilleur débit en utilisant le moins de RBs. A partir de ce procédé, quatre algorithmes d'optimisation sont proposés: l’algorithme glouton statique, PexaCol statique, PexaCol dynamique et PexaCol dynamique approximatif. L'analyse des résultats montre que pour les petits clusters, les versions statiques et dynamiques de PexaCol permettent d'obtenir un index d’optimisation maximal en choisissant la meilleure topologie locale pour chaque noeud. A l'opposé, les algorithmes "glouton statique" et "PexaCol dynamique approximatif" permettent d'obtenir une solution sous-optimale pour l'optimisation locale avec une complexité moindre. Pour les grands clusters, avec certaine séquence de la coloration, le PexaCol dynamique approximatif est mieux que l’algorithme glouton statique pour l’index d’optimisation pendant un temps d’exécution acceptable. / Graph coloring problem is a famous NP-complete problem, which has extensive applications. In the thesis, new exact graph coloring algorithms are researched from a graph structure point of view. Based on Total solutions Exact graph Coloring algorithm (TexaCol) which is capable of getting all coloring solution subsets for each subgraph, two other exact algorithms, Partial best solutions Exact graph Coloring algorithm (PexaCol) and All best solutions Exact graph Coloring algorithm (AexaCol), are presented to get multiple best solutions. These two algorithms utilize the backtracking method, in which they only choose the best solution subset each step to continue the coloring until partial or all best solutions are obtained. The result analysis shows that PexaCol and AexaCol can deal with larger graphs than TexaCol and especially, AexaCol runs much faster than TexaCol and the solver Gurobi to get all best solutions.Device-to-Device (D2D) is a promising technique for the future mobile networks, such as 5th generation wireless systems (5G), and the resource allocation is one of the most crucial problems for its performance. In order to efficiently allocate radio resource for D2D links in Long-Term Evolution (LTE) system, a systematic resource allocation scheme is proposed based on D2D clusters, including the inter-cluster resource allocation and the intra-cluster resource allocation. With the cluster interference range, the inter-cluster resource allocation problem is formulated as a dynamic graph coloring problem, and a dynamic graph coloring algorithm is designed based on PexaCol. This algorithm is able to allocate radio resource to clusters while they are dynamically generated and deleted. The numerical analysis results show that this algorithm has good performance in resource utilization, runtime and scalability.For the intra-cluster resource allocation problem, a topology-based resource allocation method is designed naturally combining power allocation with Resource Block (RB) allocation. To simplify this associated optimization problem, a local optimal method is proposed, in which the best topology is chosen each step achieving the maximal throughput with the minimum number of assigned RBs. With respect to this method, four algorithms are presented: static greedy, static PexaCol, dynamic PexaCol and dynamic PexaCol approximate. Result analysis shows that for small-scale clusters, static PexaCol and dynamic PexaCol are capable of getting a maximal optimization index by locally choosing the best topology for each node while static greedy and dynamic PexaCol approximate are able to get the suboptimal solution for the local optimization with much lower complexity. For large-scale clusters, giving certain treating sequences, the dynamic PexaCol approximate performs better than static greedy regarding the optimization index within an acceptable runtime.

A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes.

The aim of this work is to understand the requirements behind Quality of Service (QoS) for Multihop Wireless Networks and evaluate the performance of different such strategies. This work starts by establishing the basis for requirement of QoS and evaluates different approaches for providing QoS. Bandwidth is selected as the most important resource amongst the resources identified for ensuring QoS. The problem is modeled as an optimization problem that tries to maximize the amount of bandwidth available in the system while providing bounds over the bandwidth available over a route. Other QoS parameters are bound by hard limits and are not involved in the optimization problem. The existence of spatial reuse rules has been established through simulations for a TCP based network. This establishes that the reuse rules are independent of the MAC and network layer protocols used. This idea is used in designing the simulations for strategies that use controlled spatial reuse and give known bounds for QoS. Simulations take the network and a set of connections to generate the best possible schedule that guarantees bandwidth to individual connections and maximizes the total number of slots used in the entire system. The total number of slots used is a measure of the bandwidth in use. The set of graphs and connections is generated by a random graph and connection generator and the data set is large enough to average the results. There are two different approaches used for scheduling the connections. The first approach uses graph coloring and provides a simpler implementation in terms of network deployments. Second approach uses on-demand slot allocation. The approaches are compared for their pros and cons. The first approach uses graph coloring to allocate fixed number of slots to each link. This makes an equivalent of a wired network with fixed bandwidth over each link. This network is simpler to operate and analyze at the cost of one time expense of graph coloring. The assumption here is that the network is static or has low mobility. The on demand approach is more flexible in terms of slot assignment and is adaptable to the changing traffic patterns. The cons are that connection establishment is more expensive in terms of bandwidth required and is more complicated and difficult to analyze. The advantages include low initial network establishment cost and accommodation of mobility.

A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes.

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

Orientador: Prof. Dr. Rafael de Mattos Grisi / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015. / Esse trabalho tem por objetivo apresentar um pouco da teoria de grafos no ensino Básico. Nele serão abordados conceitos básicos da teoria de grafos com maior enfoque sobre os grafos eulerianos e semieulerianos e o teorema das quatro cores. Apresentamos e discutimos também algumas propostas de atividades que foram e poderão ser desenvolvidas no Ensino Fundamental e Médio, possibilitando ao aluno o desenvolvimento de algumas habilidades como investigar, analisar, modelar, dentre outras. A prática dessas atividades foi realizada em uma escola da rede estadual do Estado de São Paulo com uma turma do 9o ano do Ensino Fundamental e com uma turma do 3o ano do Ensino Médio, no ano de 2014. / This work aims to present some of the so called graph theory in the Basic education. It will address the basic concepts of graph theory with greater focus on the Euler graphs and the four color theorem. We also discuss some proposals for activities that have been developed in primary and secondary education, enabling the student to develop some skills to investigate, analyze and model problems using graphs. The practice of these activities took place in a state school of São Paulo with a class of 9th graders of the elementary school and a group of the 3rd year of high school, in 2014.

Submitted by Celso Magalhaes (celsomagalhaes@ufrrj.br) on 2017-07-11T12:30:26Z No. of bitstreams: 1 2016 - Odilon Magno da Silva J?nior.pdf: 3269429 bytes, checksum: b0bdf0f0a5612790959d29453f0ac06d (MD5) / Made available in DSpace on 2017-07-11T12:30:26Z (GMT). No. of bitstreams: 1 2016 - Odilon Magno da Silva J?nior.pdf: 3269429 bytes, checksum: b0bdf0f0a5612790959d29453f0ac06d (MD5) Previous issue date: 2016-08-03 / The main objective of this work is to describe an experience with problems related to graph coloring with a group of 2nd year high school students. The survey worked with students from a private school located in the city of Volta Redonda, in the state of Rio de Janeiro. This research had the participation of 51 students aged 15 to 17 years, among boys and girls, who wanted to voluntarily participate in the extracurricular classes offered. The idea of this work is to use the fact that the basic concepts of coloring in Graph Theory are easily accessible to students, they are powerful optimization tools used by large companies and are applicable to students' everyday problems, three precious characteristics for a Professor to attract the attention of the class. In this regard, we held 8 meetings with students. At first, there was a Motivational pre-test based on Gontijo?s test in order to evaluate various aspects of the relationship of students with mathematics. In the second meeting, a Content Pre-test with everyday students' problems commonly solved by graphs' techniques, but that can also be solved without them. Over the next four meetings, classes were held in order to teach some basic techniques of graphs and discuss with students what they did on the test. After those four classes, the next meeting was used for the students to take a Content Post-test with similar problems, but with the intention of observing how the students would apply the techniques they learned. On the last meeting, the students took a Motivational Post-test, so that they could give their opinion on the activities. All data were studied, analyzed and compared in the final chapters / Este trabalho tem por principal objetivo descrever uma experi?ncia com problemas relacionados a colora??o em Grafos com um grupo de alunos do 2? ano do Ensino M?dio. A pesquisa realizada trabalhou com alunos de uma escola da rede particular, localizada no munic?pio de Volta Redonda, no estado do Rio de Janeiro. Esta pesquisa contou com a participa??o de 51 alunos na faixa et?ria de 15 a 17 anos, entre meninos e meninas, que quiseram voluntariamente participar das aulas extracurriculares oferecidas. A ideia do trabalho ? utilizar o fato de que conceitos b?sicos de colora??o em Teoria de Grafos s?o de f?cil acesso aos alunos, s?o poderosas ferramentas de Otimiza??o usadas por grandes empresas e s?o aplic?veis a problemas do cotidiano dos alunos, tr?s caracter?sticas preciosas para que um professor atraia a aten??o da classe. Neste sentido foram realizados 8 encontros com os alunos. No primeiro, foi realizado um Pr?-teste Motivacional, baseado no teste de Gontijo, com o intuito de avaliar v?rios aspectos relativos ? rela??o dos alunos com a Matem?tica. No segundo, um Pr?-teste de Conte?do, com problemas que fazem parte do dia-a-dia dos alunos e comumente resolvidos com t?cnicas de Grafos, mas que tamb?m podem ser resolvidos sem elas. Nos quatro encontros seguintes, foram realizadas aulas com o objetivo de ensinar algumas t?cnicas b?sicas de Grafos e comentar com os alunos o que eles fizeram no teste. Depois das aulas, no pen?ltimo encontro foi realizado um P?s-teste de Conte?do, com quest?es similares ao primeiro, mas com o intuito de observar os alunos aplicando as t?cnicas aprendidas. No ?ltimo encontro foi realizado um P?s-teste Motivacional, para que os alunos dessem suas opini?es sobre as atividades. Todos os dados foram estudados, analisados e comparados nos cap?tulos finais.

Orientador: Christiane Neme Campos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:02:03Z (GMT). No. of bitstreams: 1 Galvao_KaioKaram_M.pdf: 1971760 bytes, checksum: e2f60ab09595b03fa6da5051cd78e3f3 (MD5) Previous issue date: 2013 / Resumo: Em 1971, Fulkerson propôs a seguinte conjetura: todo grafo cúbico sem arestas de corte admite seis emparelhamentos perfeitos tais que cada aresta do grafo pertence a exatamente dois destes emparelhamentos. A Conjetura de Fulkerson tem desafiado pesquisadores desde sua publicação. Esta conjetura é facilmente verificada para grafos cúbicos 3-aresta-coloráveis. Portanto, a dificuldade do problema reside em estabelecer a conjetura para grafos cúbicos sem arestas de corte que não possuem 3-coloração de arestas. Estes grafos são chamados snarks. Nesta dissertação, a Conjetura de Fulkerson e os snarks são introduzidos com ¿ênfase em sua história e resultados mais relevantes. Alguns resultados relacionados à Conjetura de Fulkerson são apresentados, enfatizando suas conexões com outras conjeturas. Um breve histórico do Problema das Quatro Cores e suas relações com snarks também são apresentados. Na segunda parte deste trabalho, a Conjetura de Fulkerson é verificada para algumas famílias infinitas de snarks construídas com o método de Loupekine, utilizando subgrafos do Grafo de Petersen. Primeiramente, mostramos que a família dos LP0-snarks satisfaz a Conjetura de Fulkerson. Em seguida, generalizamos este resultado para a família mais abrangente dos LP1-snarks. Além disto, estendemos estes resultados para Snarks de Loupekine construídos com subgrafos de snarks diferentes do Grafo de Petersen / Abstract: In 1971, Fulkerson proposed a conjecture that states that every bridgeless cubic graph has six perfect matchings such that each edge of the graph belongs to precisely two of these matchings. Fulkerson's Conjecture has been challenging researchers since its publication. It is easily verified for 3-edge-colourable cubic graphs. Therefore, the difficult task is to settle the conjecture for non-3-edge-colourable bridgeless cubic graphs, called snarks. In this dissertation, Fulkerson's Conjecture and snarks are presented with emphasis in their history and remarkable results. We selected some results related to Fulkerson's Conjecture, emphasizing their reach and connections with other conjectures. It is also presented a brief history of the Four-Colour Problem and its connections with snarks. In the second part of this work, we verify Fulkerson's Conjecture for some infinite families of snarks constructed with Loupekine's method using subgraphs of the Petersen Graph. More specifically, we first show that the family of LP0-snarks satisfies Fulkerson's Conjecture. Then, we generalise this result by proving that Fulkerson's Conjecture holds for the broader family of LP1-snarks. We also extend these results to even more general Loupekine Snarks constructed with subgraphs of snarks other than the Petersen Graph / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes. / Graduate Studies, College of (Okanagan) / Graduate