Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/71148| Tipo: | Tese |
| Título : | O número b-cromático de alguns gráficos em forma de árvore |
| Otros títulos : | Le nombre b-chromatique de quelques classes de graphes généralisant les arbres |
| Título en inglés: | The b-chromatic number of some tree-like graphs |
| Autor : | Silva, Ana Shirley Ferreira da |
| Tutor: | Maffray, Frédéric |
| Palabras clave : | Número b-cromático;Grafo planar externo;Grafo de blocos;Produto cartesiano;b-Chromatic number;Outerplanar graph;Block graph;Cartesian product |
| Fecha de publicación : | 24-nov-2010 |
| Citación : | SILVA, Ana Shirley Ferreira da. Le nombre b-chromatique de quelques classes de graphes généralisant les arbres. 2010. 187 f. Tese (Doutorado em Matemática e Informática) - Université de Grenoble, França, 2010. |
| Resumen en portugués brasileño: | Uma coloração de vértice de um grafo G é chamada de coloração b se cada classe de cor contém pelo menos um vértice que tem um vizinho em todas as outras classes de cores. O número b-cromático χb(G) de G é o maior inteiro k para o qual G tem uma b-coloração com k cores. Esses conceitos foram introduzidos por Irving e Manlove em 1999. Eles permitem a análise do desempenho de alguns algoritmos de coloração. Irving e Manlove mostraram que encontrar o número b-cromático é NPdifícil para grafos gerais, enquanto pode ser encontrado em tempo polinomial para árvores. Uma questão que surge naturalmente é investigar os grafos que possuem uma “estrutura de árvore”, por exemplo: cactos, grafos cordais, grafos série-paralelos, grafos de blocos, etc. Nesta tese, generalizamos o resultado de Irving e Manlove para cactos com “m-grau” pelo menos 7 e para grafos ultraplanares com perímetro pelo menos 8. (O m-grau m(G) é o maior inteiro d tal que G tem pelo menos d vértices de grau pelo menos d − 1.) Provamos um resultado similar para o produto cartesiano de uma árvore por um caminho, um ciclo ou uma estrela. Com relação a grafos cujos blocos são cliques, mostramos que o problema de parâmetros fixos pode ser resolvido em tempo polinomial e apresentamos casos onde o problema de decisão pode ser resolvido. No entanto, descobrimos que a diferença m(G) − χb(G) pode ser arbitrariamente grande para grafos de blocos, o que mostra que a estrutura da árvore não é suficiente para ter χb(G) ≥ m(G) − 1. |
| Abstract: | A vertex colouring of a graph G is called a b-colouring if each colour class contains at least one vertex that has a neighbour in all other colour classes. The b-chromatic number χb(G) of G is the largest integer k for which G has a b-colouring with k colours. These concepts have been introduced by Irving and Manlove in 1999. They allow the analisys of the performance of some algorithms for colouring. Irving and Manlove showed that finding the b-chromatic number is NPhard for general graphs, while it can be found in polynomial time for trees. A question that naturally arises is to investigate the graphs that have a “tree structure”, for instance: cactus, chordal graphs, series-parallel graphs, block graphs, etc. In this thesis, we generalize the result of Irving and Manlove for cacti with “m-degree” at least 7 and for outerplanar graphs with girth at least 8. (The m-degree m(G) is the largest integer d such that G has at least d vertices of degree at least d − 1.) We prove a similar result for the cartesian product of a tree by a path, a cycle or a star. Regarding graphs whose blocks are cliques, we show that the fixed-parameter problem can be solved in polynomial time and we present cases where the decision problem can be solved. However, we found that the difference m(G) − χb(G) can be arbitrarily large for block graphs, which shows that the tree structure is not sufficient for having χb(G) ≥ m(G) − 1. |
| Resumen en francés: | Une coloration des sommets de G s’appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique χb(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d’évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d’un graphe est un problème NP-difficile et qu’il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d’enquêter sur les graphes qui ont une structure proche des arbres: cactus, graphes triangulés, graphes série-parallèles, “block” graphes, etc. Dans cette thèse, nous généralisons le résultat d’Irving et Manlove pour les cactus dont le “m-degré” est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degr´e m(G) est le plus grand entier d tel que G a au moins d sommets de degr´e au moins d − 1.) Nous démontrons un résultat semblable pour le produit cartésien d’un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G) − χb(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu’avoir une structure arborescence n’est pas suffisant pour que le graphe satisfasse χb(G) ≥ m(G) − 1. |
| URI : | http://www.repositorio.ufc.br/handle/riufc/71148 |
| Aparece en las colecciones: | DMAT - Teses defendidas em outras instituições |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| tese_2010_asfsilva.pdf | 1,17 MB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.