Decomposition of bounded degree graphs into C4-free subgraphs

Consultar RECERCAT

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

Título:	Decomposition of bounded degree graphs into C4-free subgraphs
Autor/a:	Kang, Ross; 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 prove that every graph with maximum degree ∆ admits a partition of its edges into O(√∆) parts (as ∆→∞) none of which contains C4 as a subgraph. This bound is sharp up to a constantfactor. Our proof uses an iterated random colouring procedure.Keywords: edge-colouring, graph decomposition, graphs of bounded maximum degree, degree Ramsey numbers,bipartite Turán numbers. MSC: 05C15, 05D40, 05C35, 05C55.
Materia(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria -Combinatorial analysis -edge-colouring -graph decomposition -graphs of bounded maximum degree -degree Ramsey numbers -bipartite Turán number -Anàlisi combinatòria
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: