Scholarlink

<p>A conflict-free coloring of a graph <i>G</i> ensures that each vertex has at least one color appearing uniquely in its open neighborhood. In contrast, a list coloring provides each vertex with a list of possible colors and mandates that the vertex be colored with a color from this list. By merging these two concepts, a list conflict-free coloring is achieved when each vertex is colored with a color from its list and also has at least one color appearing uniquely in its open neighborhood. In this paper, we prove that every planar graph admits a list conflict-free 12-coloring. This finding enhances a previous result by Cheilaris, Smorodinsky, and Sulovský, which established that every planar graph on <i>n</i> vertices admits a list conflict-free (4 ln <i>n</i> + 1)-coloring.</p>

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

List conflict-free Coloring of Planar Graphs

  • 期刊论文

  • 发表日期：

    2025年12月8日

查看全文
  • Ya-li Wu,
  • Xin Zhang

摘要

A conflict-free coloring of a graph G ensures that each vertex has at least one color appearing uniquely in its open neighborhood. In contrast, a list coloring provides each vertex with a list of possible colors and mandates that the vertex be colored with a color from this list. By merging these two concepts, a list conflict-free coloring is achieved when each vertex is colored with a color from its list and also has at least one color appearing uniquely in its open neighborhood. In this paper, we prove that every planar graph admits a list conflict-free 12-coloring. This finding enhances a previous result by Cheilaris, Smorodinsky, and Sulovský, which established that every planar graph on n vertices admits a list conflict-free (4 ln n + 1)-coloring.