An acyclic edge coloring of a graph G colors the edges in G such that adjacent edges receive distinct colors and the subgraph induced by the edges of any two colors is acyclic. It is conjectured that every simple graph with maximum degree \(\varDelta \) can be acyclically edge \((\varDelta + 2)\) -colored. The conjecture has been proven true on triangle-free planar graphs, but is unknown true or not for general planar graphs. We make a step forward to acyclically edge color triangle-free toroidal graphs in \(\varDelta + 2\) colors. This improves the latest \((\varDelta + 3)\) -coloring scheme by Chen and Hou, and completely resolves affirmatively the conjecture on such a super class of triangle-free planar graphs. We achieve the result by first showing that every triangle-free toroidal graph has one of the five specified groups of local structures, and then inductively coloring the edges at the presence of each local structure.

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

Acyclically Edge Color Triangle-free Toroidal Graphs in  \(\varDelta + 2\) Colors

  • Qiaojun Shu,
  • Guohui Lin

摘要

An acyclic edge coloring of a graph G colors the edges in G such that adjacent edges receive distinct colors and the subgraph induced by the edges of any two colors is acyclic. It is conjectured that every simple graph with maximum degree \(\varDelta \) can be acyclically edge \((\varDelta + 2)\) -colored. The conjecture has been proven true on triangle-free planar graphs, but is unknown true or not for general planar graphs. We make a step forward to acyclically edge color triangle-free toroidal graphs in \(\varDelta + 2\) colors. This improves the latest \((\varDelta + 3)\) -coloring scheme by Chen and Hou, and completely resolves affirmatively the conjecture on such a super class of triangle-free planar graphs. We achieve the result by first showing that every triangle-free toroidal graph has one of the five specified groups of local structures, and then inductively coloring the edges at the presence of each local structure.