<p>An injective edge-coloring of a graph <i>G</i> is an edge-coloring <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\phi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϕ</mi> </math></EquationSource> </InlineEquation> of <i>G</i>, not necessarily proper, such that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\phi (e_1) \ne \phi (e_2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>e</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>≠</mo> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>e</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> whenever there exists an edge <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(e_3\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>e</mi> <mn>3</mn> </msub> </math></EquationSource> </InlineEquation> adjacent to both <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(e_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>e</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(e_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>e</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>. In particular, edges in a triangle must receive distinct colors. The minimum number of colors needed in an injective edge-coloring of <i>G</i>, denoted by <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\chi _{inj}^{\prime }(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mrow> <mi mathvariant="italic">inj</mi> </mrow> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is called the injective chromatic index of <i>G</i>. In this paper, we study <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(K_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>-minor free graphs, or equivalently, graphs with treewidth at most 2. Axenovich et al. [<CitationRef CitationID="CR1">1</CitationRef>] studied the injective chromatic index of graphs with treewidth at most <i>k</i>, and their result implies that every <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(K_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>-minor free graph has injective chromatic index at most 9. This improves a linear bound established by Lv et al. [<CitationRef CitationID="CR6">6</CitationRef>] to a constant. For subcubic graphs, Kostochka et al. [<CitationRef CitationID="CR5">5</CitationRef>] showed that every subcubic planar graph has injective chromatic index at most 6, which implies that every subcubic <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(K_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>-minor free graph has injective chromatic index at most 6. In the paper, we study <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(K_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>-minor free graphs with maximum degree at most 4 and prove that every such graph has injective chromatic index at most 7.</p>

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

Injective Edge-Colorings of \(K_4\)-Minor Free Graphs

  • Fuxiang Yu,
  • Xiangqian Zhou

摘要

An injective edge-coloring of a graph G is an edge-coloring \(\phi \) ϕ of G, not necessarily proper, such that \(\phi (e_1) \ne \phi (e_2)\) ϕ ( e 1 ) ϕ ( e 2 ) whenever there exists an edge \(e_3\) e 3 adjacent to both \(e_1\) e 1 and \(e_2\) e 2 . In particular, edges in a triangle must receive distinct colors. The minimum number of colors needed in an injective edge-coloring of G, denoted by \(\chi _{inj}^{\prime }(G)\) χ inj ( G ) , is called the injective chromatic index of G. In this paper, we study \(K_4\) K 4 -minor free graphs, or equivalently, graphs with treewidth at most 2. Axenovich et al. [1] studied the injective chromatic index of graphs with treewidth at most k, and their result implies that every \(K_4\) K 4 -minor free graph has injective chromatic index at most 9. This improves a linear bound established by Lv et al. [6] to a constant. For subcubic graphs, Kostochka et al. [5] showed that every subcubic planar graph has injective chromatic index at most 6, which implies that every subcubic \(K_4\) K 4 -minor free graph has injective chromatic index at most 6. In the paper, we study \(K_4\) K 4 -minor free graphs with maximum degree at most 4 and prove that every such graph has injective chromatic index at most 7.