TAILIEUCHUNG - Báo cáo toán học: "On (δ, χ)-bounded families of graphs"

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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On (δ, χ)-bounded families of graphs. | On 8 x -bounded families of graphs András Gyárfás Manouchehr Zaker Computer and Automation Research Institute Department of Mathematics Hungarian Academy of Sciences Institute for Advanced Studies in Budapest . Box 63 Basic Sciences IASBS Budapest Hungary H-1518 Zanjan 45137-66731 Iran gyarfas@ mzaker@ Submitted Jun 7 2010 Accepted May 1 2011 Published May 8 2011 Mathematics Subject Classification 05C15 05C35 Abstract A family F of graphs is said to be Ỗ x -bounded if there exists a function f x satisfying f x TO as x -TO such that for any graph G from the family one has f Ỗ G x G where Ỗ G and x G denotes the minimum degree and chromatic number of G respectively. Also for any set Hl H2 . Hk of graphs by Forb Hl H2 . Hk we mean the class of graphs that contain no Hi as an induced subgraph for any i 1 . k. In this paper we first answer affirmatively the question raised by the second author by showing that for any tree T and positive integer Forb T Kụ is a Ỗ x -bounded family. Then we obtain a necessary and sufficient condition for Forb H1 H2 . Hk to be a Ỗ x -bounded family where H1 H2 . Hk is any given set of graphs. Next we study Ỗ x -boundedness of Forb C where C is an infinite collection of graphs. We show that for any positive integer Forb Kfự C6 C8 . is Ỗ x -bounded. Finally we show a similar result when C is a collection consisting of unicyclic graphs. 1 Introduction A family F of graphs is said to be 8 x -bounded if there exists a function f x satisfying f x - TO as x TO such that for any graph G from the family one has f 8 G x G where 8 G and x G denotes the minimum degree and chromatic number of G respectively. Equivalently the family F is 8 x -bounded if 8 Gn - TO implies x Gn - TO for any sequence G1 G2 . with Gn G F. Motivated by Problem in 6 the second author introduced and studied 8 x -bounded families of graphs under the name of J-bounded families in 10 . The so-called color-bound family of graphs mentioned in the related .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học