A Conjecture of Erdos

DOI10.2307/3109808MaRDI QIDQ4222467zbMATH OpenOpenAlexWikidataFDO

Authors Ralph Faudree

Publication date 7 December 1998

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/3109808

zbMATH Keywords

conjecture of Erdősmonochromatic domination

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

A set of vertices \(A\) of a graph \(G\) dominates all vertices that are either in \(A\) or adjacent to a vertex in \(A\). If the edges of \(G\) are coloured, then a set \(A\) monochromatically dominates a set \(B\) if it dominates \(B\) in one of the subgraphs of \(G\) determined by the edges in one of the colours. This note discusses the following conjecture of Erdős and some generalizations. Conjecture. If the edges of a complete graph \(K_n\) are coloured with two colours, then for any positive integer \(t\), there is a set of \(t\) vertices that monochromatically dominate all but at most \(n/2^t\) of the vertices of \(K_n\).

Recommendations

• Domination in colored complete graphs
• A Solution to the 2/3 Conjecture
• A new bound for the 2/3 conjecture
• scientific article; zbMATH DE number 4154488
• Vertex coverings by monochromatic cycles and trees

Cited in

(5)

• An Erdős-Gallai conjecture
• Near-domination in graphs
• scientific article; zbMATH DE number 981678 (Why is no real title available?)
• Domination in colored complete graphs
• Covering 2‐colored complete digraphs by monochromatic d d‐dominating digraphs

This page was built for publication: A Conjecture of Erdos

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