Note on highly connected monochromatic subgraphs in 2-colored complete graphs

MaRDI QIDQ625377zbMATH OpenFDO

Authors Shinya Fujita, Colton Magnant

Publication date 17 February 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/223488, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p15.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

highly connected subgraphslarge monochromatic subgraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Review text

Summary: We improve upon some recent results concerning the existence of large monochromatic, highly connected subgraphs in a 2-coloring of a complete graph. In particular, we show that if \(n \geq 6.5(k - 1)\), then in any 2-coloring of the edges of \(K_n\), there exists a monochromatic \(k\)-connected subgraph of order at least \(n - 2(k - 1)\). Our result improves upon several recent results by a variety of authors.

Recommendations

• Highly connected monochromatic subgraphs of two-colored complete graphs
• Highly connected monochromatic subgraphs
• On Connected Components with Many Edges
• A note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs
• Highly connected monochromatic subgraphs of multicolored graphs

Cited in

(12)

• Highly connected subgraphs of graphs with given independence number
• Monochromatic subgraphs in the absence of a properly colored 4-cycle
• Forbidden rainbow subgraphs that force large monochromatic or multicolored \(k\)-connected subgraphs
• Forbidden properly edge-colored subgraphs that force large highly connected monochromatic subgraphs
• Highly connected monochromatic subgraphs
• A note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs
• Forbidden rainbow subgraphs that force large highly connected monochromatic subgraphs
• On the profile of multiplicities of complete subgraphs
• Highly connected subgraphs of graphs with given independence number (extended abstract)
• Highly Connected Subgraphs with Large Chromatic Number
• An upper bound for a Ramsey type problem for k-connected subgraphs
• Highly connected monochromatic subgraphs of two-colored complete graphs

This page was built for publication: Note on highly connected monochromatic subgraphs in 2-colored complete graphs

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