Sobre Grafos UEH
Autores
|
4195 |
410,931
|
|
|
6832 |
410,931
|
Informações:
Publicações do PESC
O grafo de interseção de uma família de conjuntos é o grafo obtido associando-se a cada conjunto um vértice e, tal que dois vértices são adjacentes se e somente se os conjuntos correspondentes têm interseção não vazia.
Examinamos as classes de grafos UE e UEH, que são os grafos de interseção de caminhos em uma árvore, onde os caminhos são considerados como conjuntos de arestas. Quando a família de caminhos satisfaz a propriedade Helly, temos a classe UEH.
Apresentamos uma caracterização por subgrafos proibidos para os grafos que são simultaneamente UEH e split, uma prova de que o problema da coloração de vértices para grafos UEH é NP-Completo e provamos que todo grafo UEH admite uma coloração de cliques com 3 cores mas este valor é ilimitado para grafos UE.
Neste texto também estabelecemos que os problemas sanduíche para a classe clique-Helly e para subclasses desta são NP-Completos além das relações de inclusão entre as classes UE, UEH e clique-Helly.
The intersection graph of a family of sets is obtained by associating a vertex with each set of the family and two vertices are adjacent if and only if the corresponding sets have a non empty intersection.
We examine the UE and UEH graph classes, that are intersection graphs of paths in a tree, where the paths are given by its edge sets. If the family of paths satisfies the Helly property we obtain the UEH graphs.
We present a forbidden subgraphs characterization for graphs that are both UEH and split. We prove that the vertex coloring problem for UEH graphs is NP-Complete and every UEH graph admits a clique coloring using 3 colors but this value is unbounded for UE graphs.
We also prove that the sandwich problems for the clique-Helly class and subclasses are NP-Complete as well as the inclusion relations between UE, UEH and clique-Helly classes.