Về tính duy nhất 2-tô màu danh sách của đồ thị tách cực đầy đủ

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Lê Xuân Hùng

Ngôn ngữ: vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học và Công nghệ (Đại học Đà Nẵng), 2021

Mô tả vật lý: 69-72

Bộ sưu tập: Metadata

ID: 386626

Thêm vào giỏ Liên kết toàn văn

Cho G là đồ thị có n đình và giả sử với mỗi đinh V của G , tồn tại một danh sách gồm k màu, z(v), sao cho có duy nhất một tô màu cho đồ thị G từ các danh sách màu này, khi đó G được gọi là đồ thị duy nhất k - tô màu danh sách Đồ thị G = (K, E) được gọi là đồ thị tách cực nếu tồn tại phân hoạch V = I u K sao cho đồ thị con của G cảm sinh trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ thị đầy đủ. Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi s. Foldes và P.L. Hammer. Các đồ thị này được nghiên cứu nhiều trong lý thuyết đồ thị. Đồ thị tách cực dày đủ với I/ị = = n được ký hiệu là s(m,n) . Trong bài báo này, chúng ta sẽ chứng minh được rằng 5(w,n) là duy nhất 2 - tô màu danh sách khi và chỉ khi m >
2, n >
2 .

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR