Caracterizações de convexidades geométricas de grafos - de Araújo, Rafael Teixeira; Sampaio, Rudini Menezes (Anais do Encontro de Teoria da Computação (ETC); 2016: Anais do I Encontro de Teoria da Computação, 2016)
Uma convexidade de grafos é geométrica se todo conjunto convexo é o fecho convexo de seus vértices extremos. Vários trabalhos têm caracterizado as classes de grafos para os quais uma dada convexidade é geométrica, como a convexidade monofônica em grafos cordais, a convexidade geodésica em grafos ptolemaicos [Farber and Jamison 1986] e a convexidade m3 em grafos bipolarizados fracos [Dragan et al. 1999]. Nesse artigo, obtemos caracterizações para as convexidades P3, P3 , P+4 e triangle-path. Também obtemos resultados no sentido oposto: dada uma classe de grafos, existe alguma convexidade que só é geométrica nessa classe?