Data: 24/08/2021, às 14:00 horas (GMT-3, horário de Brasília).
Título: Intersection models and forbidden pattern characterizations for k-thin and proper k-thin graphs
Palestrante: Flavia Bonomo (Universidad de Buenos Aires)
Abstract: The thinness of a graph is a width parameter introduced by Mannino, Oriolo, Ricci, and Chandran in 2007 as a generalization of interval graphs, which are exactly the 1-thin graphs. Analogously, proper thinness is defined such that graphs with bounded proper thinness generalize proper interval graphs.
When a representation of the graph as a k-thin graph is given, for a constant value k, some NP-complete problems as list matrix partition problems with bounded matrix size can be solved in polynomial time by dynamic programming.
In this talk We will present intersection models for graphs with (proper) thinness 2 and 3, and an intersection model for general values which may lead to a generalization of thinness to digraphs. We also will present forbidden pattern characterizations for 2-thin graphs and variations.