Vertex Conflict Free Connection Number

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.