Highly connected monochromatic subgraphs
Any 2-coloring of the edges of the complete graph on \(n\) vertices contains a monochromatic spanning tree, as was observed by Erdös a long time ago. Here the authors look for large monochromatic subgraphs of high vertex connectivity in an edge-2-colored \(K_n\). A large family, \(B(n,k)\), of edge-2-colored graphs on \(n\) vertices with the property that the maximal order of a \(k\)-connected monochromatic subgraph is \(n-2(k-1)\) is constructed. The authors conjecture that for \(n>4(k-1)\) every 2-colored \(K_n\) contains a \(k\)-connected monochromatic subgraph on at least \(n-2(k-1)\) vertices. If the conjecture is true, the family \(B(n,k)\) shows that it is best possible. The conjecture is proven for \( k=2 \).
- Highly connected monochromatic subgraphs of two-colored complete graphs
- Note on highly connected monochromatic subgraphs in 2-colored complete graphs
- A note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs
- Highly connected monochromatic subgraphs of multicolored graphs
- Forbidden rainbow subgraphs that force large highly connected monochromatic subgraphs
- An upper bound on the Ramsey number of trees
- Covering \(t\)-element sets by partitions
- Edge colorings of complete graphs without tricolored triangles
- scientific article; zbMATH DE number 2197938 (Why is no real title available?)
- scientific article; zbMATH DE number 3262254 (Why is no real title available?)
- Maximum degree and fractional matchings in uniform hypergraphs
- Modern graph theory
- On generalized Ramsey numbers for trees
- Partitioning by monochromatic trees
- Some notes on the Erdős-Szekeres theorem
- Vertex coverings by monochromatic cycles and trees
- Size of monochromatic double stars in edge colorings
- Highly connected coloured subgraphs via the regularity Lemma
- Monochromatic homeomorphically irreducible trees in 2-edge-colored complete graphs
- Highly connected subgraphs of graphs with given independence number
- Forbidden rainbow subgraphs that force large monochromatic or multicolored \(k\)-connected subgraphs
- Monochromatic partitions in local edge colorings
- Heterochromatic tree partition number in complete multipartite graphs
- Forbidden properly edge-colored subgraphs that force large highly connected monochromatic subgraphs
- Size of monochromatic components in local edge colorings
- A note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs
- Highly connected multicoloured subgraphs of multicoloured graphs
- Colourfully panconnected subgraphs. II.
- Forbidden rainbow subgraphs that force large highly connected monochromatic subgraphs
- Monochromatic connectivity in monochromatic-star-free graphs
- scientific article; zbMATH DE number 3851127 (Why is no real title available?)
- Large Monochromatic Components in Two-colored Grids
- Monochromatic Hamiltonian 3-tight Berge cycles in 2-colored 4-uniform hypergraphs
- Large Monochromatic Components in Two-Colored Grids
- Highly connected monochromatic subgraphs of multicolored graphs
- scientific article; zbMATH DE number 4041942 (Why is no real title available?)
- Heterochromatic tree partition problem in complete tripartite graphs
- scientific article; zbMATH DE number 840704 (Why is no real title available?)
- Highly connected subgraphs of graphs with given independence number (extended abstract)
- Long monochromatic Berge cycles in colored 4-uniform hypergraphs
- Highly Connected Subgraphs with Large Chromatic Number
- Note on highly connected monochromatic subgraphs in 2-colored complete graphs
- The power of many colours
- Balanced substructures in bicolored graphs
- 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: Highly connected monochromatic subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2477397)
