Bài viết đư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 của Chang và các cộng sự. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của bài viết này. | HNUE JOURNAL OF SCIENCE DOI Natural Sciences 2021 Volume 66 Issue 1 pp. 25-29 This paper is available online at http MỘT ĐIỀU KIỆN MỚI ĐỂ MỘT ĐỒ THỊ CÓ SỐ LIÊN THÔNG KHÔNG XUNG ĐỘT LÀ 2 Phạm Ngọc Diệp Trường Trung học phổ thông Chuyên Nguyễn Huệ 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ự. Từ khóa tô màu cạnh số liên thông không xung đột bậc của đỉnh. 1. Mở đầu Trong bài báo này để đơn giản hóa kí hiệu chúng ta kí hiệu k cho tập 1 2 . . . k với k là số nguyên dương bất kì. Chúng ta sẽ sử dụng các thuật ngữ trong tài liệu 2 cho các thuật ngữ không được định nghĩa trong bài báo. Xét một đồ thị G đơn liên thông hữu hạn và không có hướng. Ta kí hiệu tập các đỉnh tập các cạnh số các đỉnh cấp của G và số các cạnh lần lượt là V G E G n và m. Với mỗi đỉnh v V G ta kí hiệu N v là lân cận của v trong G và kí hiệu dG v N v là bậc của v trong G. Ta kí hiệu bậc nhỏ nhất của G là δ G minv V G dG v . Một cạnh của đồ thị gọi là cạnh cắt nếu chúng ta bỏ cạnh đó khỏi đồ thị vẫn giữ nguyên hai đầu mút thì đồ thị mới có số thành phần liên thông lớn hơn số thành phần liên thông của đồ thị ban đầu. Đồ thị đầy đủ cấp t được kí hiệu là Kt . Nếu u v V G là hai đỉnh phân biệt và kề nhau trong G ta thường viết uv là cạnh chứa hai đỉnh u v. Ta định nghĩa C G là đồ thị con của G cảm sinh trên tập các cạnh cắt của G. Một .
