Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 849.05021
Autor: Erdös, Paul; Füredi, Z.; Loebl, M.; Sós, V.T.
Title: Discrepancy of trees. (In English)
Source: Stud. Sci. Math. Hung. 30, No.1-2, 47-57 (1995).
Review: For a graph L let E(L) be its edge set. Let \phi: E(Kn) ––> {1, 2} be a two-coloring of the edges of the complete graph Kn and let Dn(L, \phi): = max| |\phi- 1 (1) \cap E(L^*)|- {|E(L^*)|\over 2}|, where the maximum is extended over all subgraphs L^* of Kn isomorphic to L. The discrepancy of L is defined by Dn(L): = max Dn(L, \phi), where the minimum is extended over all \phi: E(Kn) ––> {1, 2}. Let Tn be a tree on n vertices, \Delta(Tn) be the maximum degree in Tn and \tau(Tn) be the minimum size of a vertex cover in Tn. The following inequalities are proved: If \Delta(Tn) \geq 0.8n then D(Tn) \geq (n- 1- \Delta(Tn))/6, if n > m0 and \Delta(Tn) < 0.8n then D(Tn) > n· 10- 3, if \Delta(Tn), \tau(Tn) \leq k \leq n/8 then D(Tn) \geq n/2 - 4k. Several interesting problems and conjectures are mentioned.
Reviewer: K.Engel (Rostock)
Classif.: * 05C05 Trees
05C55 Generalized Ramsey theory
05D10 Ramsey theory
05C35 Extremal problems (graph theory)
Keywords: Ramsey theory; extremal graphs; edge coloring; discrepancy; tree
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag