令 G = (V, E) 是具有 n 个点、m条边的连通简单图。称图 G 是局部反魔幻的,则 G 有—个局部反魔幻标号。图 G 的局部反魔幻标号是—个双射 f : E → {1, 2, ···, m},使得对图 G 的任意两个相邻的顶点 u 和 v 都有ω(u) ≠ω(v),其中, E(u) 是与点 u 相关联的边的集合。若对图 G 的点 v 着颜色 ω(v),明显得出 G 的任—个局部反魔幻标号导出图 G 的—个正常点着色。图 G 的局部反魔幻着色数是其局部反魔幻标号中所用的最少颜色数,记为 χla(G)。给定两个点不交的图 G 和 H,图 G 和 H的联图,记为 G ∨ H,是在图 G 和 H 的基础上,再将 G 的每—个点与 H 的每—个点相连而得到的图。本文给出了路 Pn,圈 Cn,星图 Sn以及友谊图 Fn与完全图 K2 的联图的局部反魔幻着色数的确切值。
展开▼
