Về tính duy nhất 2-tô màu danh sách của đồ thị tách cực đầy đủ

Tóm tắt

Cho G là đồ thị có n đỉnh và giả sử với mỗi đỉnh v  của G, tồn tại một danh sách gồm k màu, L(v), sao cho có duy nhất một tô màu cho đồ thị G từ các danh sách màu này, khi đó G được gọi là đồ thị duy nhất k - tô màu danh sách. Đồ thị G=(V,E) được gọi là đồ thị tách cực nếu tồn tại phân hoạch V=I giao K sao cho đồ thị con của G cảm sinh trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ thị đầy đủ. Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes và P.L. Hammer. Các đồ thị này được nghiên cứu nhiều trong lý thuyết đồ thị. Đồ thị tách cực đầy đủ với I=m, K=n được ký hiệu là S(m,n). Trong bài báo này, chúng ta sẽ chứng minh được rằng  là duy nhất 2- tô màu danh sách khi và chỉ khi m>=2, n>=2 .