%0 Journal Article
%T <i>P</i><i><sub>m</sub></i>&#9633;<i>P</i><i><sub>n</sub></i>的奇染色和正常无冲突染色<br>Odd Coloring and Proper Conflict-Free Coloring of <i>P</i><i><sub>m</sub></i>&#9633;<i>P</i><i><sub>n</sub></i>
%A 王泰山
%A 方晓峰
%J Pure Mathematics
%P 211-215
%@ 2160-7605
%D 2025
%I Hans Publishing
%R 10.12677/pm.2025.151024
%X 图的染色理论在模式识别、生物信息、社交网络和电力网络上有重要的应用。对于图<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>G</mi>
</math>

的一个点染色<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>&#x03C6;</mi><mo>:</mo><mi>V</mi><mrow><mo>(</mo>
   <mi>G</mi>
  <mo>)</mo></mrow><mo>&#x2192;</mo><mrow><mo>{</mo> <mrow>
   <mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>&#x22EF;</mo><mo>,</mo><mi>k</mi></mrow> <mo>}</mo></mrow></mrow>
</math>

&#65292;若满足对任意非孤立点<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>v</mi><mo>&#x2208;</mo><mi>V</mi><mrow><mo>(</mo>
   <mi>G</mi>
  <mo>)</mo></mrow></mrow>
</math>

&#65292;都存在<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>c</mi><mo>&#x2208;</mo><mrow><mo>{</mo> <mrow>
   <mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>&#x22EF;</mo><mo>,</mo><mi>k</mi></mrow> <mo>}</mo></mrow></mrow>
</math>

使得<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mrow><mo>|</mo> <mrow>
   <msup>
    <mi>&#x03C6;</mi>
    <mrow>
     <mo>&#x2212;</mo><mn>1</mn></mrow>
   </msup>
   <mrow><mo>(</mo>
    <mi>c</mi>
   <mo>)</mo></mrow><mo>&#x2229;</mo><mi>N</mi><mrow><mo>(</mo>
    <mi>v</mi>
   <mo>)</mo></mrow></mrow> <mo>|</mo></mrow></mrow>
</math>

是一个奇数&#65292;则称<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>&#x03C6;</mi>
</math>

是图<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>G</mi>
</math>

的一个奇<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>k</mi>
</math>

-染色。特别地&#65292;若<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mrow><mo>|</mo> <mrow>
   <msup>
    <mi>&#x03C6;</mi>
    <mrow>
     <mo>&#x2212;</mo><mn>1</mn></mrow>
   </msup>
   <mrow><mo>(</mo>
    <mi>c</mi>
   <mo>)</mo></mrow><mo>&#x2229;</mo><mi>N</mi><mrow><mo>(</mo>
    <mi>v</mi>
   <mo>)</mo></mrow></mrow> <mo>|</mo></mrow><mo>=</mo><mn>1</mn></mrow>
</math>

&#65292;则称<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>&#x03C6;</mi>
</math>

是图<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>G</mi>
</math>

的一个正常无冲突<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>k</mi>
</math>

-染色。图<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>G</mi>
</math>

的奇(正常无冲突)色数是使图<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>G</mi>
</math>

有一个奇(正常无冲突) <math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>k</mi>
</math>

-染色的<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>k</mi>
</math>

的最小值&#65292;记作<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>&#x03C7;</mi>
   <mi>o</mi>
  </msub>
  <mrow><mo>(</mo>
   <mi>G</mi>
  <mo>)</mo></mrow><mrow><mo>(</mo>
%K 路&#65292
%K 笛卡尔乘积图&#65292
%K 奇染色&#65292
%K 正常无冲突染色<br>Path
%K Cartesian Product Graph
%K Odd Coloring
%K Proper Conflict-Free Coloring
%U http://www.hanspub.org/journal/PaperInformation.aspx?PaperID=106261