Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giới hạn dưới cho số sắc độ đóng gói của tích Đề-các của các chu trình
Tóm tắt
Cho G = (V, E) là một đồ thị đơn giản có bậc n và i là một số nguyên với i ≥ 1. Tập hợp X
i
⊆ V(G) được gọi là đóng gói i nếu mỗi hai đỉnh khác nhau trong X
i
cách nhau hơn i. Một màu đóng gói của G là một phân hoạch X = {X
1, X
2, …, X
k
} của V(G) sao cho mỗi lớp màu X
i
là một đóng gói i. Bậc tối thiểu k của một màu đóng gói được gọi là số sắc độ đóng gói của G, ký hiệu là χρ(G). Trong bài báo này, chúng tôi cho thấy, bằng cách sử dụng một chứng minh lý thuyết, rằng nếu q = 4t, với một số nguyên t ≥ 3, thì 9 ≤ χρ(C
4 □ C
q
). Chúng tôi cũng sẽ chỉ ra rằng nếu t là bội của bốn, thì χρ(C
4 □ C
q
) = 9.
Từ khóa
Tài liệu tham khảo
Brešar B., Klavžar S., Rall D.F., On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math., 2007, 155(17), 2303–2311
Chartrand G., Lesniak L., Zhang P., Graphs & Digraphs, 5th ed., CRC Press, Boca Raton, 2011
Ekstein J., Fiala J., Holub P., Lidický B., The packing chromatic number of the square lattice is at least 12, available at http://arxiv.org/abs/1003.2291
Fiala J., Golovach P.A., Complexity of the packing coloring problem for trees, Discrete Appl. Math., 2010, 158(7), 771–778
Fiala J., Klavžar S., Lidický B., The packing chromatic number of infinite product graphs, European J. Combin., 2009, 30(5), 1101–1113
Finbow A.S., Rall D.F., On the packing chromatic number of some lattices, Discrete Appl. Math., 2010, 158(12), 1224–1228
Goddard W., Hedetniemi S.M., Hedetniemi S.T., Harris J.M., Rall D.F., Broadcast chromatic numbers of graphs, Ars Combin., 2008, 86, 33–49
Sloper C., Broadcast-coloring in trees, Reports in Informatics, #233, University of Bergen, Bergen, 2002, available at http://www.ii.uib.no/~sloper/Papers/brep.pdf
Soukal R., Holub P., A note on packing chromatic number of the square lattice, Electron. J. Combin., 2010, 17, #17