Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/134253

Título:	Large subgraphs without short cycles
Autor/a:	Foucaud, Florent; Krivelevich, Michael; Perarnau Llobet, Guillem
Otros autores:	Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics
Abstract:	We study two extremal problems about subgraphs excluding a family F of graphs. i) Among all graphs with m edges, what is the smallest size f(m, F) of a largest F–free subgraph? ii) Among all graphs with minimum degree d and maximum degree ¿, what is the smallest minimum degree h(d, ¿, F) of a spanning F– free subgraph with largest minimum degree? These questions are easy to answer for families not containing any bipartite graph. We study the case where F is composed of all even cycles of length at most 2r, r = 2. In this case, we give bounds on f(m, F) and h(d, ¿, F) that are essentially asymptotically tight up to a logarithmic factor. In particular for every graph G, we show the existence of subgraphs with arbitrarily high girth, and with either many edges or large minimum degree. These subgraphs are created using probabilistic embeddings of a graph into extremal graphs
Materia(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Graph theory -Grafs, Teoria de
Derechos:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Tipo de documento:	Artículo - Versión presentada Artículo
Compartir:

Mostrar el registro completo del ítem