基于图运算的局部反魔幻着色数的研究

摘要

令 G = (V (G), E(G)) 是有 n 个顶点和 m 条边的简单连通图。一个双射 f : E(G) → {1, 2, ···, m} 称为图 G 的一个局部反魔幻标号,如果对于图 G 中的任意两个相邻的顶点 u 和 v 满足 ω(u)≠ω(v),这里,其中 E(u) 是与点 u 相关联的边的集合。如果给图 G 中任意一个顶点 v 着颜色 ω(v),那么图 G 的任意一个局部反魔幻标号都会导出图 G 的一个正常点着色。图 G 的局部反魔幻着色数 χla(G) 是图 G 的局部反魔幻标号所导出的所有着色中的最少颜色数。本文主要研究经过一些图运算(如:友谊图加一条悬挂边 Fn + {e} 和一些特殊图星图 Pm(Sn) 和双星图 Pm(Sl,q) 的剖分图)之后图的局部反魔幻着色问题。