аЯрЁБс>ўџ ')ўџџџ&џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№ПGbjbjqPqP8::G џџџџџџЄњњњњњњњ6666J } .bbbbbbbbќўўўўўў$Ћ h x" њbbbbb" њњbb7 XXXbrњbњbќXbќXXњњXbV №ƒяdе6дRXшM 0} X‹ &‹ XX‹ њh€bbXbbbbb" " Bbbb} bbbb$њњњњњњџџџџ Resumo: Esta tese aborda dois diferentes problemas. O primeiro щ focado na classe dos cografos, onde usamos a representaчуo de coсrvores para desenvolver um algoritmo capaz de gerar, sem isomorfismos, todos os cografos com n vщrtices, cujo tempo de geraчуo entre dois cografos consecutivos foi feito em tempo O(n). Em seguida aplicamos este procedimento para conjecturar uma nova cota para o nњmero b-cromсtico de um cografo conexo, dada em termos do raio espectral. O segundo problema abordado щ o estudo da complexidade do problema de obter o menor nњmero de cliques disjuntas em arestas necessсrias para particionar as arestas de G, chamado cp(G) Este problema jс щ conhecido como NP-completo para grafos em geral, inclusive para split, grafos K4-livres e grafos cordais. Provamos que a NP-completude щ mantida para a classe dos grafos 3-colorэveis, subclasse dos K4-livre. Alщm disso, conseguimos obter a complexidade do problema para grafos (k,l), aqueles cujo conjunto de vщrtices pode ser particionado em k independentes e l cliques, estabelecendo quando o problema щ NP-completo ou polinomial para cada k e l fixados. Palavras-chave: cografo, gerador, partiчуo de arestas em cliques, grafo-(k,l). Abstract: This thesis approaches on two different problems. The first one is focused on the class of cographs, where we use the representation of cotrees to develop an algorithm capable of generating, without isomorphisms, all the n vertex cographs and whose generation time between two consecutive cografos was done in time O(n). Then we apply this procedure to conjecture a new bound for the b-chromatic number of a connected cograph given in terms of the spectral radius. The second problem is the study of the complexity of the problem of obtaining the least number of disjoint cliques on edges necessary to partition the edges of G, called cp(G). This problem is already known as NP-complete for general graphs, including split, K4-free graphs and chordal graphs. We prove that NP-completeness is maintained for the class of 3-colorable graphs, subclass of K4-free. In addition, we get the complexity of the problem for graphs (k,l) those whose set of vertices can be partitioned into k independent and l cliques, establishing when the problem is NP-complete or polynomial for each fixed k and l. Keywords: cograph, generator, edge clique partition, (k,l)-graph. пр5 : y z „ ‰ н т ь э d e В И   [ ] g v Џ Е Ж З П Р ыкыХ­Х­Х­Х­Х­Х–Х–Х­Х­Х­Х~Х­ХыfQ)hT666666666666666666666666666Ј6666666666И666666666666hH66666666666666666666666666666666666666666666666666666666666666666А6R@ёџR Normal dЄ  CJPJ^J_HaJmHsHtH >AђџЁ> 0Fonte parсg. padrуoTiѓџГT 0 Tabela normalі4ж l4жaі ,kєџС, 0 Sem lista ЂeђЂ Zu0Prщ-formataчуo HTMLA Ц2”(М Pфx  4 Ш#\'№*„.2Ќ5@9d№Є CJOJQJ^JaJmHsHtH`ўЂ` ;1Ц0HTML Preformatted CharCJOJPJQJ^JaJtH <ўђџ< Zu0 Char CharOJPJQJ^JG џџџџfgЖЗС I ˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€I Kˆ0№MР G G G V^ˆвк grЁЈ18_j„†ЌЗнтў#ISф№3>w~ ЇЗП$IPˆ”ЇЏтъcjЈЏ\_  ; > I kmГЕАВЗС<?< > I 33ЗСI ЗПI gtсXх— !Y*g'ПD,;l,wp1T