Highly connected monochromatic subgraphs of multicolored graphs

DOI10.1002/JGT.20365MaRDI QIDQ3633005zbMATH OpenOpenAlexFDO

Authors

Publication date 16 June 2009

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

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) Connectivity (05C40) Generalized Ramsey theory (05C55)

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.

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

Cites work

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

Cited in

(21)

• Highly connected multicoloured subgraphs of multicoloured graphs
• Large monochromatic triple stars in edge colourings
• 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
• On some multicolor Ramsey properties of random graphs
• Long monochromatic paths and cycles in 2-colored bipartite graphs
• Highly connected monochromatic subgraphs of multicolored graphs
• Highly connected monochromatic subgraphs
• Highly connected monochromatic subgraphs of two-colored complete graphs
• Highly connected coloured subgraphs via the regularity Lemma
• Estimation of cut-vertices in edge-coloured complete graphs
• 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)
• Note on highly connected monochromatic subgraphs in 2-colored complete graphs
• 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)