: 10h15, ngày 18/05/2020 (Thứ Hai)
: P106 D3
: Seminar Toán rời rạc
: Nguyễn Anh Tú
: KSTN K60
Tóm tắt báo cáo
Một đường đi trên một đồ thị tô màu đỉnh được gọi là không giao tranh (conflict-free) nếutrên đường đi đó tồn tại đỉnh được tô một màu duy nhất. Một đồ thị tô màu đỉnh được gọilà không giao tranh đỉnh liên thông nếu giữa hai đỉnh bất kì của đồ thị, tồn tại một đường đikhông giao tranh. Bài báo cáo này quan tâm đến số màu không giao tranh đỉnh liên thôngcủa đồ thị, tức là với một đồ thị liên thông G, ta cần phải tô ít nhất bao nhiêu màu để G trở thành một đồ thị không giao tranh đỉnh liên thông.