Thinness 2 condicionada a ´ordenes de co-bipartici´on

Resumen

En este trabajo nos enfocamos en la caracterización por patrones prohibidos de las clases de grafos definidas por su thinness, un parámetro de ancho definido por Mannino, Oriolo, Ricci y Chandran. Concretamente, trabajamos en la caracterización por patrones prohibidos minimales de la clase de grafos co-bipartitos 2-thin condicionados. Para llegar a dicha caracterización definimos, en este trabajo, los conceptos de orden bisagra y representación 2-thin condicionada. El primer concepto define un ordenamiento de los vértices a partir de su orden y partición 2-thin; y el segundo define restricciones en dicho orden. Logramos identificar una propiedad general para grafos con thinness a lo sumo 2 con la cual probamos que, dado un orden bisagra asociado a una representación 2-thin, definir dos clases partiendo ese orden en cualquier punto que para la primera clase defina un orden canónico de intervalos y para la segunda clase el reverso de un tal orden, produce otra representación 2-thin cuyo orden bisagra es el mismo. Con dicho resultado probamos que, dado un grafo co-bipartito 2-thin condicionado, existe una representación 2-thin del grafo con orden bisagra condicionado y tal que cada clase es un completo. Además obtuvimos que las aristas incidentes a las dos clases inducen un bigrafo de intervalos.