Decomposition of bounded degree graphs into C4-free subgraphs

Inici | Què és? | Contacte

English | Castellano

Consultar RECERCAT

Per comunitats i
col·leccions Per data Per autors Per títols Per matèries

Consultar col·lecció

Per data Per autors Per títols Per matèries

Estadístiques

Del document Tot RECERCAT

El meu RECERCAT

Entrar Alertes per correu-e

Directori d’altres repositoris

Pàgina inicial del RECERCAT > Universitat Politècnica de Catalunya > Documents de recerca > Visualitza document

Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/134251

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor	Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics
dc.contributor.author	Kang, Ross
dc.contributor.author	Perarnau Llobet, Guillem
dc.date	2014-10-15
dc.identifier.citation	Kang, R.; Perarnau-Llobet, G. Decomposition of bounded degree graphs into C4-free subgraphs. "European journal of combinatorics", 15 Octubre 2014, vol. 44, núm. Part A, p. 99-105.
dc.identifier.citation	0195-6698
dc.identifier.citation	10.1016/j.ejc.2014.09.009
dc.identifier.uri	http://hdl.handle.net/2117/134251
dc.language.iso	eng
dc.relation	https://www.sciencedirect.com/science/article/pii/S019566981400153X
dc.rights	Attribution-NonCommercial-NoDerivs 3.0 Spain
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria
dc.subject	Combinatorial analysis
dc.subject	edge-colouring
dc.subject	graph decomposition
dc.subject	graphs of bounded maximum degree
dc.subject	degree Ramsey numbers
dc.subject	bipartite Turán number
dc.subject	Anàlisi combinatòria
dc.title	Decomposition of bounded degree graphs into C4-free subgraphs
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/article
dc.description.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.

Mostra el registre simple del document

Documents relacionats

Altres documents del mateix autor/a

An interlacing approach for bounding the sum of Laplacian eigenvalues of graphs

Abiad, Aida; Fiol Mora, Miquel Àngel; Haemers, Willem H.; Perarnau Llobet, Guillem

Large subgraphs without short cycles

Foucaud, Florent; Krivelevich, Michael; Perarnau Llobet, Guillem

Fast recoloring of sparse graphs

Bousquet, Nicolas; Perarnau Llobet, Guillem

Acyclic edge colourings of graphs with large girth

Cai, Xing Shi; Perarnau Llobet, Guillem; Reed, Bruce; Watts, Adam Bene

On the treewidth and related parameters of random geometric graphs

Mitsche, Dieter; Perarnau Llobet, Guillem

Accessibilitat | Avís legal | Política de Cookies | Documents d'ús intern

Coordinació

Patrocini