<p>A <i>k</i>-injective-edge coloring of a graph <i>G</i> is an edge coloring c: <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(E(G)\rightarrow \{1,2,\cdots ,k\}\)</EquationSource> </InlineEquation>, such that if <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(e_{1}\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(e_{2}\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(e_{3}\)</EquationSource> </InlineEquation> are three consecutive edges in <i>G</i>, then <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(c(e_{1})\ne c(e_{3})\)</EquationSource> </InlineEquation>, where <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(e_{1}\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(e_{2}\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(e_{3}\)</EquationSource> </InlineEquation> are consecutive if they form a path or a cycle of length 3. The minimum integer <i>k</i> such that <i>G</i> has a <i>k</i>-injective-edge coloring is called the injective chromatic index of <i>G</i>, denoted by <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\chi '_{i}(G)\)</EquationSource> </InlineEquation>. The maximum average degree of <i>G</i>, denoted by mad(<i>G</i>), is defined to be the maximum average over all subgraphs <i>H</i> of <i>G</i>. In this paper, I will consider the injective edge coloring of sparse graph <i>G</i> with maximum degree 5. I get that (1) if mad <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\((G)&lt;\frac{31}{8}\)</EquationSource> </InlineEquation>, then <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\chi '_{i}(G)\le 20\)</EquationSource> </InlineEquation>; (2) if mad <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\((G)&lt;4\)</EquationSource> </InlineEquation>, then <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\chi '_{i}(G)\le 21\)</EquationSource> </InlineEquation>.</p>

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

On injective edge coloring of sparse graphs with maximum degree 5

  • Yanqing Wu

摘要

A k-injective-edge coloring of a graph G is an edge coloring c: \(E(G)\rightarrow \{1,2,\cdots ,k\}\) , such that if \(e_{1}\) , \(e_{2}\) and \(e_{3}\) are three consecutive edges in G, then \(c(e_{1})\ne c(e_{3})\) , where \(e_{1}\) , \(e_{2}\) and \(e_{3}\) are consecutive if they form a path or a cycle of length 3. The minimum integer k such that G has a k-injective-edge coloring is called the injective chromatic index of G, denoted by \(\chi '_{i}(G)\) . The maximum average degree of G, denoted by mad(G), is defined to be the maximum average over all subgraphs H of G. In this paper, I will consider the injective edge coloring of sparse graph G with maximum degree 5. I get that (1) if mad \((G)<\frac{31}{8}\) , then \(\chi '_{i}(G)\le 20\) ; (2) if mad \((G)<4\) , then \(\chi '_{i}(G)\le 21\) .