Strong flip-flatness has emerged as a natural dense analogue of uniform almost-wideness in the context of preservation theorems, but its combinatorial meaning is still not fully understood. In this paper, we study strongly flip-flat graph classes under a weak sparsity assumption, namely the exclusion of a fixed biclique as a subgraph. Our main result shows that a graph class is weakly sparse and strongly flip-flat if and only if it is uniformly almost-wide. The proof transforms bounded families of flips into bounded deletion sets proceeding via an induction on the number of flips rather than on the independence radius. This viewpoint yields a new connection between flip-based decompositions in dense settings and wideness notions from sparse graph theory. As a consequence, we obtain a characterization of strongly flip-flat classes inside structurally bounded expansion classes, confirming the corresponding case of a broader conjecture that strongly flip-flat classes should be exactly the structurally uniformly almost-wide classes.
(Fatemeh Ghasemi) [LACL, Université Paris-Est Créteil]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .