Đa thức màu

Trong lý thuyết đồ thị, Đa thức màu (tiếng Anh: Chromatic polynomial) của một đồ thị biểu diễn số cách tô màu các đỉnh của đồ thị đó theo số màu. Đa thức màu là đối tượng nghiên cứu của lý thuyết đại số đồ thị, một nhánh của toán học.

Đa thức màu được đề xuất bởi Geogre David Birkhoff trong một nỗ lực của ông nhằm giải quyết bài toán định lý bốn màu.

Lịch sử

Geogre David Birkhoff đưa ra khái niệm đa thức màu vào năm 1912. Lúc đó, nó chỉ được định nghĩa cho các đồ thị phẳng nhằm giải quyết bài toán định lý bốn màu, ý tưởng của Birkhoff như sau:

mọi đồ thị phẳng G đều có sắc số không lớn hơn 4, nếu P ( G , 4 ) > 0 {\displaystyle P(G,4)>0} với mọi G, trong đó P(G,k) xác định số cách tô màu đỉnh G bởi k màu.

Vào năm 1932, Hassler Whitney đã mở rộng khái niệm đa thức màu cho đồ thị bất kì. Đến năm 1968, Read đặt câu hỏi: "liệu có tiêu chuẩn nào để xác định một đa thức cho trước có là đa thức màu hay không?". Câu hỏi này đến nay vẫn còn đang bị bỏ ngỏ. Chính vì vậy, người ta phải định nghĩa đa thức màu thông qua đồ thị.

Ngày nay, đa thức màu là đối tượng nghiên cứu trung tâm của lý thuyết đồ thị đại số.

Định nghĩa

Giá trị của đa thức màu của đồ thị G tại k bằng số cách tô màu đỉnh đồ thị G với k màu. Đa thức màu thường được ký hiệu là P G ( k ) {\displaystyle P_{G}(k)} , χ G ( k ) {\displaystyle _{G}(k)} , hoặc π G ( k ) {\displaystyle _{G}(k)} hoặc đôi khi là P ( G , k ) {\displaystyle P(G,k)} .

Ví dụ:

  • Đồ thị đường đi P 3 {\displaystyle P_{3}} có đa thức màu là:
P P 3 ( k ) = k ⋅ ( k − 1 ) 2 {\displaystyle P_{P_{3}}(k)=k\cdot (k-1)^{2}} .
Không thể tô màu đỉnh P 3 {\displaystyle P_{3}} chỉ với 0 hoặc 1 màu, P P 3 ( 0 ) = P P 3 ( 1 ) = 0 {\displaystyle P_{P_{3}}(0)=P_{P_{3}}(1)=0} .
Có 2 cách tô màu đỉnh P 3 {\displaystyle P_{3}} bằng 2 màu, P P 3 ( 2 ) = 2 {\displaystyle P_{P_{3}}(2)=2} .
Có 12 cách tô màu đỉnh P 3 {\displaystyle P_{3}} bằng 3 màu, P P 3 ( 3 ) = 12 {\displaystyle P_{P_{3}}(3)=12} .

Sắc số có thể định nghĩa theo đa thức màu như sau:

sắc số của đồ thị G là giá trị nguyên dương nhỏ nhất k mà đa thức màu của G tại k nhận giá trị dương:
χ ( G ) = m i n k : P G ( k ) > 0 {\displaystyle (G)=min{k:P_{G}(k)>0}} .

Ví dụ

Đa thức màu của một số đồ thị
Đồ thị tam giác K 3 {\displaystyle K_{3}} k ( k − 1 ) ( k − 2 ) {\displaystyle k(k-1)(k-2)}
Đồ thị đường đi P n {\displaystyle P_{n}} k ( k − 1 ) n − 1 {\displaystyle k(k-1)^{n-1}}
Đồ thị đầy đủ K n {\displaystyle K_{n}} k ( k − 1 ) ( k − 2 ) … ( k − ( n − 1 ) ) {\displaystyle k(k-1)(k-2)\dots (k-(n-1))}
Cây với n {\displaystyle n} đỉnh k ( k − 1 ) n − 1 {\displaystyle k(k-1)^{n-1}}
Đồ thị chu trình C n {\displaystyle C_{n}} ( k − 1 ) n + ( − 1 ) n ( k − 1 ) {\displaystyle (k-1)^{n}+(-1)^{n}(k-1)}
Đồ thị Petersen k ( k − 1 ) ( k − 2 ) ( k 7 − 12 k 6 + 67 k 5 − 230 k 4 + 529 k 3 − 814 k 2 + 775 k − 352 ) {\displaystyle k(k-1)(k-2)(k^{7}-12k^{6}+67k^{5}-230k^{4}+529k^{3}-814k^{2}+775k-352)}

Xem thêm

Chú thích

Tham khảo

Liên kết ngoài