On incidence coloring conjecture in Cartesian products of graphs

详细信息    查看全文

• 作者：Petr Gregor^a ; ^{gregor@ktiml.mff.cuni.cz" class="auth_mail" title="E-mail the corresponding author} ; Borut Lužar^b ; ^{borut.luzar@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Roman Sotá ; k^c ; ^{roman.sotak@upjs.sk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Incidence coloring ; Cartesian product ; Locally injective homomorphism
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 November 2016
• 年：2016
• 卷：213
• 期：Complete
• 页码：93-100
• 全文大小：442 K

文摘

An incidence   in a graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si3.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=60d249ed9f7d6c465c11239430bc7ea7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a pair class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si18.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=28f603e683e4b777ab8ca4dae129881c" title="Click to view the MathML source">(v,e)class="mathContainer hidden">class="mathCode">$(v,e)$ where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si19.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=9a37fefd76d62d413db6053ae1cbb233" title="Click to view the MathML source">vclass="mathContainer hidden">class="mathCode">$v$ is a vertex of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si3.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=60d249ed9f7d6c465c11239430bc7ea7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si21.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=3809cf4d3369df05695ff4b595e562b0" title="Click to view the MathML source">eclass="mathContainer hidden">class="mathCode">$e$ is an edge of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si3.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=60d249ed9f7d6c465c11239430bc7ea7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ incident to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si19.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=9a37fefd76d62d413db6053ae1cbb233" title="Click to view the MathML source">vclass="mathContainer hidden">class="mathCode">$v$. Two incidences class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si18.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=28f603e683e4b777ab8ca4dae129881c" title="Click to view the MathML source">(v,e)class="mathContainer hidden">class="mathCode">$(v,e)$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si25.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=6cf78acd4a7ed03f44222aac7194d907" title="Click to view the MathML source">(u,f)class="mathContainer hidden">class="mathCode">$(u,f)$ are adjacent   if at least one of the following holds: class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si26.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=31b46bbec75bd63f11bdea18f8591fd4">class="imgLazyJSB inlineImage" height="15" width="64" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302025-si26.gif">class="mathContainer hidden">class="mathCode">, class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si27.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=1fdf6516c9493e914d16f8b37ee558d4">class="imgLazyJSB inlineImage" height="15" width="61" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302025-si27.gif">class="mathContainer hidden">class="mathCode">, or class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si28.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=2a99b0535aa44b2ef44f19e4c0a39587">class="imgLazyJSB inlineImage" height="15" width="96" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302025-si28.gif">class="mathContainer hidden">class="mathCode">. An incidence coloring   of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si3.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=60d249ed9f7d6c465c11239430bc7ea7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si30.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=dac9808ba23f8dd374ac711577643ebd" title="Click to view the MathML source">Δ(G)+2class="mathContainer hidden">class="mathCode">$\Delta \left(G\right)+2$ colors are needed for an incidence coloring of any graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si3.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=60d249ed9f7d6c465c11239430bc7ea7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$. The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si3.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=60d249ed9f7d6c465c11239430bc7ea7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ for which class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si3.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=60d249ed9f7d6c465c11239430bc7ea7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ admits an incidence coloring with at most class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302025&_mathId=si30.gif&_user=111111111&_pii=S0166218X16302025&_rdoc=1&_issn=0166218X&md5=dac9808ba23f8dd374ac711577643ebd" title="Click to view the MathML source">Δ(G)+2class="mathContainer hidden">class="mathCode">$\Delta \left(G\right)+2$ colors.