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

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

Tác giả: Xuân Hùng Lê

Ngôn ngữ: vie

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

Thông tin xuất bản: Tạp chí Khoa học - Đại học Đà Lạt, 2020

Mô tả vật lý: 85-93

Bộ sưu tập: Metadata

ID: 493672

Thêm vào giỏ

Cho G là đồ thị có n đỉnh. Giả sử với mỗi đỉnh v của G, tồn tại một danh sách L(v) gồm k màu, 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 được gọi là đồ thị tách cực nếu tồn tại phân hoạch V = I È 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 bởi Foldes và Hammer (1977). Các đồ thị này được nghiên cứu nhiều trong lý thuyết đồ thị. Bài báo này sẽ nghiên cứu tính chất của đồ thị tách cực đầy đủ khi nó là duy nhất k-tô màu danh sách.

1. Đọc trực tuyến

1. Đọc trực tuyến

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