Monochromatic components in edge-coloured graphs with large minimum degree

DOI10.37236/9039MaRDI QIDQ2223462zbMATH OpenOpenAlexFDO

Authors Hannah Guggiari, Alex Scott

Publication date 29 January 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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

Gyárfás-Sárközy conjecturelargest monochromatic component

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55)

Abstract: For every $ninmathbbN$ and $kgeq2$, it is known that every $k$-edge-colouring of the complete graph on $n$ vertices contains a monochromatic connected component of order at least $fracnk-1$. For $kgeq3$, it is known that the complete graph can be replaced by a graph $G$ with $delta(G)geq(1-varepsilo{n}_k)n$ for some constant $varepsilo{n}_k$. In this paper, we show that the maximum possible value of $varepsilo{n}_3$ is $frac16$. This disproves a conjecture of Gy'{a}rfas and S'{a}rk"{o}zy.

Review text

Summary: For every \(n\in\mathbb{N}\) and \(k\geqslant 2\), it is known that every \(k\)-edge-colouring of the complete graph on \(n\) vertices contains a monochromatic connected component of order at least \(\frac{n}{k-1} \). For \(k\geqslant 3\), it is known that the complete graph can be replaced by a graph \(G\) with \(\delta(G)\geqslant(1-\varepsilon_k)n\) for some constant \(\varepsilon_k\). In this paper, we show that the maximum possible value of \(\varepsilon_3\) is \(\frac16\). This disproves a conjecture of \textit{A. Gyárfás} and \textit{G. Sárközy} [ibid. 24, No. 3, Research Paper P3.54, 14 p. (2017; Zbl 1369.05076)].

Recommendations

• Large monochromatic components in edge colored graphs with a minimum degree condition
• Large monochromatic components in 3-colored non-complete graphs
• Large monochromatic components in almost complete graphs and bipartite graphs
• On Connected Components with Many Edges
• Large monochromatic components in multicolored bipartite graphs

Cites work

• Large monochromatic components in 3-colored non-complete graphs
• Large monochromatic components in edge colored graphs with a minimum degree condition
• Large monochromatic components in edge colorings of graphs: A survey
• Large monochromatic components in multicolored bipartite graphs
• Long monochromatic paths and cycles in 2-colored bipartite graphs
• Star versus two stripes Ramsey numbers and a conjecture of Schelp

Cited in

(16)

• Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs
• The order of monochromatic subgraphs with a given minimum degree
• Large monochromatic components in almost complete graphs and bipartite graphs
• Large monochromatic components in edge colored graphs with a minimum degree condition
• Forbidden properly edge-colored subgraphs that force large highly connected monochromatic subgraphs
• Colourings with Bounded Monochromatic Components in Graphs of Given Circumference
• Color degree and monochromatic degree conditions for short properly colored cycles in edge‐colored graphs
• A new bound for the 2/3 conjecture
• Large monochromatic components in multicolored bipartite graphs
• Large monochromatic components of small diameter
• Large monochromatic components in hypergraphs with large minimum codegree
• On Connected Components with Many Edges
• Large monochromatic components in 3‐edge‐colored Steiner triple systems
• Large monochromatic components in expansive hypergraphs
• A note about monochromatic components in graphs of large minimum degree
• Large monochromatic components in 3-colored non-complete graphs

This page was built for publication: Monochromatic components in edge-coloured graphs with large minimum degree

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