TAILIEUCHUNG - 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

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.