MỘT ĐIỀU KIỆN MỚI ĐỂ MỘT ĐỒ THỊ CÓ SỐ LIÊN THÔNG KHÔNG XUNG ĐỘT LÀ 2

DOI: 10.18173/2354-1059.2021-0003

  • Phạm Ngọc Diệp
Từ khóa: tô màu cạnh, số liên thông không xung đột, bậc của đỉnh.

Tóm tắt

Trong đồ thị có các cạnh được tô màu, một đường được gọi là không xung đột nếu có màu được sử dụng trên các cạnh của đường đó duy nhất một lần. Một đồ thị có các cạnh được tô màu được gọi là đồ thị liên thông không xung đột nếu hai đỉnh bất kì của đồ thị được nối với nhau bởi ít nhất một đường liên thông không xung đột. Đặt cf c(G) là số màu nhỏ nhất sao cho ta có thể dùng các màu đó để tô các cạnh của đồ thị G sao cho G là đồ thị liên thông không xung đột. Trong bài báo này, chúng tôi sẽ đưa ra một điều kiện về bậc nhỏ nhất của đồ thị liên thông không đầy đủ G để G có cf c(G) = 2. Kết quả đạt được là một mở rộng của một kết quả trong bài báo [1] của Chang và các cộng sự.

điểm /   đánh giá
Phát hành ngày
2021-07-21
Chuyên mục
BAI BÁO