Cho trước graph http://dientuvietnam...etex.cgi?G=(V,E).Nếu cần ít nhất http://dientuvietnam...n/mimetex.cgi?n màu để tô màu các đỉnh của graph sao cho giữa hai đỉnh cùng màu không có cạnh nào nối chúng,thì graph gọi là http://dientuvietnam...cgi?n-màu.Chứng minh rằng với mỗi số nguyên dương http://dientuvietnam...n/mimetex.cgi?n ,có ít nhất một graph http://dientuvietnam...metex.cgi?n-màu mà không có tam giác.
Nhìn lại tất cả các bài toán của China TST 1993
#2
Đã gửi 22-12-2005 - 09:52
garabond
-
- Thành viên
-
- 4 Bài viết
Lính mới
Tôi có 1 lời giải cho bài này , nhưng khá dài và phức tạp .Hi vọng được tham khảo 1 lời giải hay hơn.....
#3
Đã gửi 22-12-2005 - 11:23
lavieestunemerde
-
- Founder
-
- 104 Bài viết
Trung sĩ
Bài này chắc là cổ lắm rồi vì có trong AMM năm 52 hay 53 gì đó. Giờ vẫn còn hơi nhớ loáng thoáng lời giải 
#4
Đã gửi 22-12-2005 - 19:58
QUANVU
-
- Hiệp sỹ
-
- 4378 Bài viết
B&S-D
Vậy ngày kia nhờ cả hai người đăng lời giải của mình biết được không? 
1728
#5
Đã gửi 10-01-2006 - 09:33
lavieestunemerde
-
- Founder
-
- 104 Bài viết
Trung sĩ
Cách xây dựng này (cọp được trên net) chính là cách mà hồi trước em thấy (do Blanches Descartes, "bút danh" của Tutte, xây dựng).
Let G be an n-vertex graph with girth at least six and chromatic number k ≥ 2. Form a new graph H as follows. Take C(n,kn) disjoint copies of G and a set S of kn vertices, and set up a one-one correspondence between the copies of G and the n-element subsets ofS. For each copy of G, join its vertices to the members of the corresponding n-element subset of S by a matching. Show that H has chromatic number at least k + 1 and girth at least six.
Về sau Mycielski (1955) có cách xây dựng đơn giản hơn :
Mycielski’s Construction: From a simple graph G, Mycielski’s Construction produces a simple graph G’ containing G. Beginning with G having vertex set {v1, v2, …,vn}, add vertices U={u1, u2, …,un} and one more vertex w. Add edges to make ui adjacent to all of NG(vi), and finally let NG’(w)=U (vừa mới cọp về, chưa xem
)
Xem thêm tại http://mathworld.wol...elskiGraph.html
Let G be an n-vertex graph with girth at least six and chromatic number k ≥ 2. Form a new graph H as follows. Take C(n,kn) disjoint copies of G and a set S of kn vertices, and set up a one-one correspondence between the copies of G and the n-element subsets ofS. For each copy of G, join its vertices to the members of the corresponding n-element subset of S by a matching. Show that H has chromatic number at least k + 1 and girth at least six.
Về sau Mycielski (1955) có cách xây dựng đơn giản hơn :
Mycielski’s Construction: From a simple graph G, Mycielski’s Construction produces a simple graph G’ containing G. Beginning with G having vertex set {v1, v2, …,vn}, add vertices U={u1, u2, …,un} and one more vertex w. Add edges to make ui adjacent to all of NG(vi), and finally let NG’(w)=U (vừa mới cọp về, chưa xem
)Xem thêm tại http://mathworld.wol...elskiGraph.html
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh
