<p>Let <i>G</i> = (<i>V, E</i>) be a simple graph and ϕ: <i>V</i>(<i>G</i>) ⋃ <i>E</i>(<i>G</i>) → {1, 2, ⋯, <i>k</i>} be a proper total-<i>k</i>-coloring of <i>G</i>. Let <i>f</i>(<i>v</i>) = <i>ϕ</i>(<i>v</i>)Π<sub>uv∈<i>E</i>(G)</sub><i>ϕ</i>(<i>uv</i>). The coloring <i>ϕ</i> is neighbor product distinguishing if <i>f</i>(<i>u</i>) ≠ <i>f</i>(<i>v</i>) for each edge <i>uv</i> ∈ <i>E</i>(<i>G</i>). The neighbor product distinguishing total chromatic number of <i>G</i>, denoted by <i>χ</i><Stack> <sub>Π</sub> <sup>″</sup> </Stack>(<i>G</i>), is the smallest integer <i>k</i> such that <i>G</i> admits a <i>k</i>-neighbor product distinguishing total coloring. Li et al. conjectured that <i>χ</i><Stack> <sub>Π</sub> <sup>″</sup> </Stack>(<i>G</i>) ≤ Δ(<i>G</i>) + 3 for any graph with at least two vertices and confirmed the conjecture for <i>K</i><sub>4</sub>-minor free graph. In this paper, we prove that for a graph <i>G</i> with at least two vertices, (1) if mad <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1025_Article_IEq1.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="63" /> </InlineMediaObject> <EquationSource Format="TEX">\((G)&lt;{60 \over 17}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mrow> <mfrac> <mn>60</mn> <mn>17</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, then <i>χ</i><Stack> <sub>Π</sub> <sup>″</sup> </Stack>(<i>G</i>) ≤ max{Δ + 2, 8}; (2) if mad <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1025_Article_IEq2.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\((G)&lt;{8 \over 3}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mrow> <mfrac> <mn>8</mn> <mn>3</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, then <i>χ</i><Stack> <sub>Π</sub> <sup>″</sup> </Stack>(<i>G</i>) ≤ max{Δ + 2, 6}. Furthermore, by using the Combinatorial Nullstellensatz, we simplify their proof and show that <i>χ</i><Stack> <sub>Π</sub> <sup>″</sup> </Stack>(<i>G</i>) ≤ max{Δ(<i>G</i>) + 2, 6} for any <i>K</i><sub>4</sub>-minor free graph.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Neighbor Product Distinguishing Total Coloring via Combinatorial Nullstellensatz

  • Meng-ying Shi,
  • Li Zhang

摘要

Let G = (V, E) be a simple graph and ϕ: V(G) ⋃ E(G) → {1, 2, ⋯, k} be a proper total-k-coloring of G. Let f(v) = ϕ(vuv∈E(G)ϕ(uv). The coloring ϕ is neighbor product distinguishing if f(u) ≠ f(v) for each edge uvE(G). The neighbor product distinguishing total chromatic number of G, denoted by χ Π (G), is the smallest integer k such that G admits a k-neighbor product distinguishing total coloring. Li et al. conjectured that χ Π (G) ≤ Δ(G) + 3 for any graph with at least two vertices and confirmed the conjecture for K4-minor free graph. In this paper, we prove that for a graph G with at least two vertices, (1) if mad \((G)<{60 \over 17}\) ( G ) < 60 17 , then χ Π (G) ≤ max{Δ + 2, 8}; (2) if mad \((G)<{8 \over 3}\) ( G ) < 8 3 , then χ Π (G) ≤ max{Δ + 2, 6}. Furthermore, by using the Combinatorial Nullstellensatz, we simplify their proof and show that χ Π (G) ≤ max{Δ(G) + 2, 6} for any K4-minor free graph.