MỘT LƯU Ý VỀ SỐ KẾT NỐI KHÔNG XUNG ĐỘT THÍCH HỢP CỦA CÁC ĐỒ THỊ LIÊN THÔNG

Tóm tắt

Cho ???? là một đồ thị được tô màu tất cả các cạnh. Một đường trong đồ thị ???? được gọi là đường không xung đột nếu trên đó có một màu sử dụng chính xác một lần duy nhất. Đồ thị ???? được gọi là liên thông không xung đột nếu cứ hai đỉnh khác nhau bất kỳ trong đồ thị được kết nối với ít nhất một đường không xung đột. Đồ thị ???? được gọi là tô màu thích hợp, khi đó các màu được tô cho các cạnh của đồ thị sao cho không có cạnh nào cùng kề với một đỉnh nhận màu giống nhau. Nếu đồ thị ???? vừa là đồ thị thỏa mãn đồng thời điều kiện tô màu thích hợp và liên thông không xung đột thì các tác giả tại [1] đã giới thiệu khái niệm mới là liên thông không xung đột thích hợp. Số liên thông không xung đột thích hợp, được ký hiệu là ????????????????(????), là số màu nhỏ nhất cần phải tô tất cả các cạnh của đồ thị sao cho đồ thị trở thành liên thông không xung đột thích hợp. Hiện nay, có rất ít kết quả về số liên thông không xung đột thích hợp. Trong bài báo này, chúng tôi xác định số liên thông không xung đột thích hợp của một số lớp đồ thị liên thông thỏa mãn ????????????????(????) = ????′(????).