{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:02Z","timestamp":1753893782246,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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$. In [3] Erd\u0151s and Gy\u00e1rf\u00e1s studied this function if $p$ and $q$ are fixed and $n$ tends to infinity. They determined for every $p$ the smallest $q$ ($= {p \\choose 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 perhaps this is the only $q$ value which results in a linear $f(n,p,q)$. In this paper we study the behavior of $f(n,p,q)$ between the linear and quadratic orders of magnitude. In particular we show that that we can have at most $\\log p$ values of $q$ which give a linear $f(n,p,q)$.<\/jats:p>","DOI":"10.37236\/1553","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T21:09:39Z","timestamp":1578690579000},"source":"Crossref","is-referenced-by-count":8,"title":["On Edge Colorings with at Least q Colors in Every Subset of p Vertices"],"prefix":"10.37236","volume":"8","author":[{"given":"G\u00e1bor N.","family":"S\u00e1rk\u00f6zy","sequence":"first","affiliation":[]},{"given":"Stanley","family":"Selkow","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2000,12,7]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v8i1r9\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v8i1r9\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,18]],"date-time":"2020-01-18T00:20:39Z","timestamp":1579306839000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v8i1r9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,12,7]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2001,1,1]]}},"URL":"https:\/\/doi.org\/10.37236\/1553","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2000,12,7]]},"article-number":"R9"}}