Decomposition of bounded degree graphs into C4-free subgraphs

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/134251

Title:	Decomposition of bounded degree graphs into C4-free subgraphs
Author:	Kang, Ross; Perarnau Llobet, Guillem
Other authors:	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.
Subject(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
Rights:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Document type:	Article - Submitted version Article
Share: