<p>Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G=(V,E,c)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo>,</mo> <mi>c</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be an edge-colored graph, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(c:E\rightarrow \mathbb {N}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>:</mo> <mi>E</mi> <mo stretchy="false">→</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> is an edge coloring of <i>G</i>. Let <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(d_G^{c}(v)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>d</mi> <mi>G</mi> <mi>c</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> be the color degree of <i>v</i>, which is the number of distinct colors on incident edges of <i>v</i>. Let <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\delta ^{c}(G)=\min \{d_G^{c}(v)~|~v\in V(G)\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mo movablelimits="true">min</mo> <mrow> <mo stretchy="false">{</mo> <msubsup> <mi>d</mi> <mi>G</mi> <mi>c</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> <mspace width="3.33333pt" /> <mo stretchy="false">|</mo> <mspace width="3.33333pt" /> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> be the minimum color degree of <i>G</i> (with respect to <i>c</i>). Let <i>s</i>, <i>t</i> be two integers with <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(s\ge t\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo>≥</mo> <mi>t</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <i>G</i> be an edge-colored graph with <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\delta ^{c}(G)\ge s+t+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>s</mi> <mo>+</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Fujita, Li and Wang in 2019 conjectured that <i>G</i> admits a partition (<i>S</i>,&#xa0;<i>T</i>) such that <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\delta ^{c}(G[S])\ge s\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mrow> <mo stretchy="false">[</mo> <mi>S</mi> <mo stretchy="false">]</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\delta ^{c}(G[T])\ge t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mrow> <mo stretchy="false">[</mo> <mi>T</mi> <mo stretchy="false">]</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>. Here <i>G</i>[<i>U</i>] denotes the subgraph of <i>G</i> induced by the vertex set <i>U</i>. Let <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(E^{i}=\{e\in E(G)~|~c(e)=i\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>E</mi> <mi>i</mi> </msup> <mo>=</mo> <mrow> <mo stretchy="false">{</mo> <mi>e</mi> <mo>∈</mo> <mi>E</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mspace width="3.33333pt" /> <mo stretchy="false">|</mo> <mspace width="3.33333pt" /> <mi>c</mi> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>i</mi> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> be the color class for color <i>i</i>, let <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(G^{i}=(V(G),E^{i})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>G</mi> <mi>i</mi> </msup> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> <msup> <mi>E</mi> <mi>i</mi> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> be the corresponding subgraph. A bipartite graph <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(K_{1,3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> is called a claw, and a graph is claw-free if it does not contain a claw as an induced subgraph. We say an edge-colored graph <i>G</i> is a (monochromatic claw)-free graph if for each <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(i\in \mathbb {N}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(G^{i}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>G</mi> <mi>i</mi> </msup> </math></EquationSource> </InlineEquation> is claw-free. In this paper, we first show that a (monochromatic claw)-free graph <i>G</i> admits a partition (<i>S</i>,&#xa0;<i>T</i>) such that <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\delta ^{c}(G[S])\ge s\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mrow> <mo stretchy="false">[</mo> <mi>S</mi> <mo stretchy="false">]</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\delta ^{c}(G[T])\ge t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mrow> <mo stretchy="false">[</mo> <mi>T</mi> <mo stretchy="false">]</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation> if <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(\delta ^{c}(G)\ge 2s+t+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mn>2</mn> <mi>s</mi> <mo>+</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. A monochromatic path of length 2 is referred to as a monochromatic 2-path. Let <i>G</i> be an edge-colored graph in which no end-vertex of a monochromatic 2-path lies on another monochromatic 2-path of a different color. Then, we show that such an edge-colored graph <i>G</i> admits a partition (<i>S</i>,&#xa0;<i>T</i>) such that <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\delta ^{c}(G[S])\ge s\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mrow> <mo stretchy="false">[</mo> <mi>S</mi> <mo stretchy="false">]</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(\delta ^{c}(G[T])\ge t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mrow> <mo stretchy="false">[</mo> <mi>T</mi> <mo stretchy="false">]</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation> if <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(\delta ^{c}(G)\ge s+t+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>δ</mi> <mi>c</mi> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>s</mi> <mo>+</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Partitioning Edge-Colored Graphs with Constrained Color Degrees

  • Ma Huawen

摘要

Let \(G=(V,E,c)\) G = ( V , E , c ) be an edge-colored graph, where \(c:E\rightarrow \mathbb {N}\) c : E N is an edge coloring of G. Let \(d_G^{c}(v)\) d G c ( v ) be the color degree of v, which is the number of distinct colors on incident edges of v. Let \(\delta ^{c}(G)=\min \{d_G^{c}(v)~|~v\in V(G)\}\) δ c ( G ) = min { d G c ( v ) | v V ( G ) } be the minimum color degree of G (with respect to c). Let s, t be two integers with \(s\ge t\ge 2\) s t 2 and G be an edge-colored graph with \(\delta ^{c}(G)\ge s+t+1\) δ c ( G ) s + t + 1 . Fujita, Li and Wang in 2019 conjectured that G admits a partition (ST) such that \(\delta ^{c}(G[S])\ge s\) δ c ( G [ S ] ) s and \(\delta ^{c}(G[T])\ge t\) δ c ( G [ T ] ) t . Here G[U] denotes the subgraph of G induced by the vertex set U. Let \(E^{i}=\{e\in E(G)~|~c(e)=i\}\) E i = { e E ( G ) | c ( e ) = i } be the color class for color i, let \(G^{i}=(V(G),E^{i})\) G i = ( V ( G ) , E i ) be the corresponding subgraph. A bipartite graph \(K_{1,3}\) K 1 , 3 is called a claw, and a graph is claw-free if it does not contain a claw as an induced subgraph. We say an edge-colored graph G is a (monochromatic claw)-free graph if for each \(i\in \mathbb {N}\) i N , \(G^{i}\) G i is claw-free. In this paper, we first show that a (monochromatic claw)-free graph G admits a partition (ST) such that \(\delta ^{c}(G[S])\ge s\) δ c ( G [ S ] ) s and \(\delta ^{c}(G[T])\ge t\) δ c ( G [ T ] ) t if \(\delta ^{c}(G)\ge 2s+t+1\) δ c ( G ) 2 s + t + 1 . A monochromatic path of length 2 is referred to as a monochromatic 2-path. Let G be an edge-colored graph in which no end-vertex of a monochromatic 2-path lies on another monochromatic 2-path of a different color. Then, we show that such an edge-colored graph G admits a partition (ST) such that \(\delta ^{c}(G[S])\ge s\) δ c ( G [ S ] ) s and \(\delta ^{c}(G[T])\ge t\) δ c ( G [ T ] ) t if \(\delta ^{c}(G)\ge s+t+1\) δ c ( G ) s + t + 1 .