Highly connected monochromatic subgraphs of multicolored graphs

DOI10.1002/JGT.20365zbMATH Open1202.05079arXivmath/0702354OpenAlexW4242795750MaRDI QIDQ3633005FDOQ3633005

Author name not available (Why is that?)

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

Recommendations

• Highly connected multicoloured subgraphs of multicoloured graphs
• Highly connected monochromatic subgraphs of two-colored complete graphs
• Highly connected monochromatic subgraphs
• On Connected Components with Many Edges
• Highly connected coloured subgraphs via the regularity Lemma

zbMATH Keywords

\(k\)-connected graphedge graph coloring

Mathematics Subject Classification ID

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

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

Cited In (18)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3633005)