Highly connected monochromatic subgraphs of multicolored graphs

DOI10.1002/JGT.20365zbMath1202.05079arXivmath/0702354OpenAlexW4242795750MaRDI QIDQ3633005

No author found.

Publication date: 16 June 2009

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We consider the following question of Bollobas: given an r-colouring of the edges of the complete graph on n vertices, how large a k-connected subgraph can we find using only one colour? We solve this problem asymptotically when r-1 is a prime power, and exactly for 2- and 3-colourings.

Full work available at URL: https://arxiv.org/abs/math/0702354

zbMATH Keywords

\(k\)-connected graphedge graph coloring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Connectivity (05C40)

Cites Work

• Maximum degree and fractional matchings in uniform hypergraphs
• Highly connected monochromatic subgraphs
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Highly connected monochromatic subgraphs of multicolored graphs

Related Items (17)

Improved monochromatic double stars in edge colorings ⋮ Large monochromatic components and long monochromatic cycles in random hypergraphs ⋮ Large Monochromatic Triple Stars in Edge Colourings ⋮ Forbidden properly edge-colored subgraphs that force large highly connected monochromatic subgraphs ⋮ Long monochromatic paths and cycles in 2-colored bipartite graphs ⋮ On some Multicolor Ramsey Properties of Random Graphs ⋮ Forbidden rainbow subgraphs that force large monochromatic or multicolored \(k\)-connected subgraphs ⋮ Highly connected monochromatic subgraphs of two-colored complete graphs ⋮ Monochromatic partitions in local edge colorings ⋮ The power of many colours ⋮ Highly connected subgraphs of graphs with given independence number ⋮ Partitioning random graphs into monochromatic components ⋮ Highly connected subgraphs of graphs with given independence number (extended abstract) ⋮ A note on 2-edge-colorings of complete graphs with small monochromatic \(k\)-connected subgraphs ⋮ Highly connected monochromatic subgraphs of multicolored graphs ⋮ Large monochromatic components in 3-colored non-complete graphs ⋮ Highly connected coloured subgraphs via the regularity Lemma

This page was built for publication: Highly connected monochromatic subgraphs of multicolored graphs