tailieunhanh - Báo cáo toán học: "On edge colorings with at least q colors in every subset of p vertices"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On edge colorings with at least q colors in every subset of p vertices | On edge colorings with at least q colors in every subset of p vertices Gábor N. Sarkozy Stanley Selkow Computer Science Department Worcester Polytechnic Institute Worcester MA 01609 gsarkozy@ sms@ Submitted April 26 2000 Accepted December 7 2000. Abstract For fixed integers p and q an edge coloring of Kn is called a p q -coloring if the edges of Kn 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 Kn. In 3 Erdos and Gyarfas studied this function if p and q are fixed and n tends to infinity. They determined for every p the smallest q 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 . 1 Introduction Notations and definitions For basic graph concepts see the monograph of Bollobas 1 . V G and E G denote the vertex-set and the edge-set of the graph G. Kn is the complete graph on n vertices. In this paper log n denotes the base 2 logarithm. pr n denotes the parity of the natural number n so it is 1 if n is odd and 0 otherwise. Edge colorings with at least q colors in every subset of p vertices The following interesting concepts were created by Erdos Elekes and Fiiredi see 2 and then later studied by Erdos and Gyarfas in 3 see also 4 . For fixed integers p and q an edge coloring of Kn is called a p q -coloring if in every subset of p vertices at least q THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R9 1 distinct colors appear on the edges. Let f n p q be the smallest number of colors needed for a P q -coloring of Kn. It will be always assumed that p 3 and 2 q p . We restrict our attention to the case when