A Solution to the 2/3 Conjecture

DOI10.1137/130926614zbMATH Open1298.05099arXiv1306.6202OpenAlexW2044216784WikidataQ123236178 ScholiaQ123236178MaRDI QIDQ3192162FDOQ3192162

Authors: Rahil Baber, John Talbot 

Publication date: 26 September 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We prove a vertex domination conjecture of ErdH os, Faudree, Gould, Gy'arf'as, Rousseau, and Schelp, that for every n-vertex complete graph with edges coloured using three colours there exists a set of at most three vertices which have at least 2n/3 neighbours in one of the colours. Our proof makes extensive use of the ideas presented in "A New Bound for the 2/3 Conjecture" by Kr'al', Liu, Sereni, Whalen, and Yilma.

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

Recommendations

• A new bound for the 2/3 conjecture
• On the \(1/3-2/3\) conjecture
• A proof of the multiplicative 1-2-3 conjecture
• On the 1-2-3-conjecture
• scientific article; zbMATH DE number 3986073
• The \(3n+1\)-conjecture
• Solution to a conjecture by Hofmeier-Wittstock
• scientific article; zbMATH DE number 3895733
• On the role of 3's for the 1-2-3 conjecture
• On a total version of 1-2-3 conjecture

zbMATH Keywords

Ramsey theoryvertex domination

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Cited In (16)

• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• Decomposing graphs into edges and triangles
• On the algebraic and topological structure of the set of Turán densities
• C5 ${C}_{5}$ is almost a fractalizer
• Further results on an equitable 1-2-3 conjecture
• A new bound for the 2/3 conjecture
• Minimum number of edges that occur in odd cycles
• Finitely forcible graphons with an almost arbitrary structure
• Weak regularity and finitely forcible graph limits
• Finitely forcible graphons and permutons
• Domination in colored complete graphs
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Inducibility of directed paths
• Finitely forcible graph limits are universal
• Rainbow triangles in three-colored graphs
• Compactness and finite forcibility of graphons

Uses Software

• CSDP
• DensityChecker

This page was built for publication: A Solution to the 2/3 Conjecture

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