本科图论讨论班（六) 组合零点定理及其应用 Combinatorial Nullstellensatz
本科图论讨论班（六） 组合零点定理及其应用 Combinatorial Nullstellensatz
定义1：无环图G的一个正常k-边染色是指一个映射 c:E(G)-->{1,2,,k} 使得对于G中任意两条相邻的边e1和e2,有 c(e1)≠c(e2) 如果G有一个正常k-边染色，则称G是k-边可染的。 5-边可染
定义 1：无环图 G 的一个正常 k-边染色是指一个映射 c：E(G) ---> {1,2,…,k} 使得对于 G 中任意两条相邻的边 e1和 e2，有 c(e1)≠c(e2) 如果 G 有一个正常 k-边染色，则称 G 是 k-边可染的
定义2：G的边色数是指G为k-边可染的最小整数k的 值，记为X'(G) -边可染 3-边可染 ?-边可柒 X'(c4)=2
定义 2：G 的边色数是指 G 为 k-边可染的最小整数 k 的 值，记为 '(G)
定义3：赋予图G的每条边e一个颜色集合/列表L(e), 如果对于图G中任何两条相邻的边e1与e2,都存在 c(e)∈L(e),c(e2)∈L(e2) 使得 c(e1)≠c(e2) 则称图G是L-边可染的。 02,4 ②3) ,④
定义 3：赋予图 G 的每条边 e 一个颜色集合/列表 L(e)， 如果对于图 G 中任何两条相邻的边 e1与 e2，都存在 c(e1)∈L(e1)，c(e2)∈L(e2) 使得 c(e1)≠c(e2) 则称图 G 是 L-边可染的
定义4：如果对于图G中的任何边e的颜色列表满足 L(e川=k,则称边列表L为一个边k-列表。 .2 ,2 13 5.6 1,21 f1.2} f3、4 以上边列表都是边2-☑引废
定义 4：如果对于图 G 中的任何边 e 的颜色列表满足 |L(e)|=k，则称边列表 L 为一个边 k-列表