Packing chromatic number, on id-i-eq1"> on-source format-t-e-x" xmlns:search="http://marklogic.com/appservices/search">\(\mathbf (1, 1, 2, 2) \) -colorings, and characterizing the Petersen graph

详细信息    查看全文

• 作者：Boštjan Brešar ; Sandi Klavžar ; Douglas F. Rall ; Kirsti Wash
• 关键词：Packing chromatic number ; Cubic graph ; Subdivision ; S ; coloring ; Generalized prism ; Petersen graph
• 刊名：Aequationes mathematicae
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：91
• 期：1
• 页码：169-184
• 全文大小：<len>
• 刊物类别：Mathematics and Statistics
• 刊物主题：Analysis; Combinatorics;
• 出版者：Springer International Publishing
• ISSN：1420-8903
• 卷排序：91

文摘

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(\Pi _1,\ldots ,\Pi _k\), where \(\Pi _i\), \(i\in [k]\), is an i-packing. The following conjecture is posed and studied: if G is a subcubic graph, then \(\chi _{\rho }(S(G))\le 5\), where S(G) is the subdivision of G. The conjecture is proved for all generalized prisms of cycles. To get this result it is proved that if G is a generalized prism of a cycle, then G is (1, 1, 2, 2)-colorable if and only if G is not the Petersen graph. The validity of the conjecture is further proved for graphs that can be obtained from generalized prisms in such a way that one of the two n-cycles in the edge set of a generalized prism is replaced by a union of cycles among which at most one is a 5-cycle. The packing chromatic number of graphs obtained by subdividing each of its edges a fixed number of times is also considered.