A note on the Grundy number and graph products

详细信息    查看全文

• 作者：Nancy E. Clarke^a ; ^{nancy.clarke@acadiau.ca" class="auth_mail" title="E-mail the corresponding author} ; Stephen Finbow^b ; ^{sfinbow@stfx.ca" class="auth_mail" title="E-mail the corresponding author} ; Shannon Fitzpatrick^c ; ^{sfitzpatrick@upei.ca" class="auth_mail" title="E-mail the corresponding author} ; Margaret-Ellen Messinger^d ; ^{mmessinger@mta.ca" class="auth_mail" title="E-mail the corresponding author} ; Rebecca Milley^e ; ^{rmilley@grenfell.mun.ca" class="auth_mail" title="E-mail the corresponding author} ; Richard J. Nowakowski^f ; ^{rjn@mathstat.dal.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Colouring ; Grundy ; Products
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 March 2016
• 年：2016
• 卷：202
• 期：Complete
• 页码：1-7
• 全文大小：416 K

文摘

A proper colouring is referred to as a Grundy colouring, or first-fit colouring if every vertex has a neighbour from each of the colour classes lower than its own. The Grundy number of a graph is the maximum class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15004254&_mathId=si2.gif&_user=111111111&_pii=S0166218X15004254&_rdoc=1&_issn=0166218X&md5=a17001c967a47f38d599f3d116cb033a" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ (number of colours) such that a Grundy colouring exists.

In this note, we determine lower and upper bounds for the Grundy number of strong products of graphs, which lead to exact values for the product of some graph classes. We also provide an upper bound on the Grundy number of the strong product of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15004254&_mathId=si3.gif&_user=111111111&_pii=S0166218X15004254&_rdoc=1&_issn=0166218X&md5=ac7cefe4f6ffacdecff204992e165b07" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ paths of length 2, which generalizes to an upper bound on the Grundy number of the strong product of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15004254&_mathId=si3.gif&_user=111111111&_pii=S0166218X15004254&_rdoc=1&_issn=0166218X&md5=ac7cefe4f6ffacdecff204992e165b07" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ stars.