On edge colorings with at least q colors in every subset of p vertices

MaRDI QIDQ1594601zbMATH OpenFDO

Authors Gábor N. Sárközy, Stanley Selkow

Publication date 8 February 2001

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

Full work available at URL http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r9.html

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

edge coloringmonochromatic matchingprobabilistic upper bound

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Review text

For fixed integers \(p\) and \(q\), an edge coloring of \(K_{n}\) is called a \((p,q)\)-coloring if the edges of \(K_{n}\) in every subset of \(p\) vertices are colored with at least \(q\) distinct colors. Let \(f(n,p,q)\) be the smallest number of colors needed for a \((p,q)\)-coloring of \(K_{n}\). \textit{P. Erdős} and \textit{A. Gyárfás} [Combinatorica 17, No. 4, 459-467 (1997; Zbl 0910.05034)] studied this function if \(p\) and \(q\) are fixed and \(n\) tends to infinity. They determined for every \(p\) the smallest \(q\) \((=p(p-1)/2-p+3)\) for which \(f(n,p,q)\) is linear in \(n\) and the smallest \(q\) for which \(f(n,p,q)\) is quadratic in \(n\). They raised the question whether this is the only \(q\) value which results in a linear \(f(n,p,q)\). In this paper the behavior of \(f(n,p,q)\) between the linear and the quadratic order of magnitude is studied. In particular it is shown that we can have at most \(\log p\) values of \(q\) which give a linear \(f(n,p,q)\), where \(\log p\) denotes the base 2 logarithm.

Recommendations

• The Erdős-Gyárfás problem on generalized Ramsey numbers
• An explicit edge-coloring of K_n with six colors on every K₅
• Edge-coloring cliques with three colors on all 4-cliques
• scientific article; zbMATH DE number 2197930
• A variant of the classical Ramsey problem

Cited in

(23)

• A variant of the classical Ramsey problem
• Edge-coloring cliques with three colors on all 4-cliques
• Generalized Ramsey numbers: forbidding paths with few colors
• An explicit edge-coloring of K_n with six colors on every K₅
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• scientific article; zbMATH DE number 3536122 (Why is no real title available?)
• scientific article; zbMATH DE number 1052839 (Why is no real title available?)
• An application of the regularity lemma in generalized Ramsey theory
• Essentially Infinite Colourings of Graphs
• Color isomorphic even cycles and a related Ramsey problem
• Local properties via color energy graphs and forbidden configurations
• scientific article; zbMATH DE number 2197930 (Why is no real title available?)
• Almost-rainbow edge-colorings of some small subgraphs
• Edge-coloring cliques with many colors on subcliques
• Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorable
• Rainbow subgraphs in edge-colored planar and outerplanar graphs
• Lower bounds on the Erdős–Gyárfás problem via color energy graphs
• The Erdős–Gyárfás function with respect to Gallai‐colorings
• New bounds on the generalized Ramsey number \(f(n, 5, 8)\)
• The Erdős-Gyárfás function \(f(n, 4, 5) = \frac{5}{6} n + o(n)\) -- so Gyárfás was right
• Growth rates of the bipartite Erdős-Gyárfás function
• Generalized Ramsey numbers at the linear and quadratic thresholds
• More distinct distances under local conditions

This page was built for publication: On edge colorings with at least \(q\) colors in every subset of \(p\) vertices

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