The stipulation polynomial of a uniquely list-colorable graph
The stipulation polynomial of a uniquely list-colorable graph
复制标题
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
J. Dinitz;W. Martin
中科院分区：
文献类型：
--
作者：
J. Dinitz;W. Martin
设G是图，S是一组冒号列表，如果G的每个顶点都取其颜色，则称G在顶点G是S列表可染的.艾伦和塔西！证明了图G是S列表可染的当且仅当它的图多项式FC(；1；..)：=IT(XJ)I~J不在由点处可得的零化子多项式颜色生成的理想I中.我们考虑G是列表可染的情形，并确定了剩余多项式(或规定多项式)1c=fa mod J的不可约.我们在G的因子和边之间建立了一个双射.
Let G be graph and let S be a set of lists of colon; at the vertices G is said to be S list-colorable if there exists a proper' /'rllnr"'Hl of G sllch that each vertexi takes its color . Alan and Tarsi! I] have shown that G is S list-colorable if and only if its graph polynomial fC(;1;..):= IT(Xi Xj) i~J does not lie in the ideal I generated by the annihilator polynomials colors available at the vertices. of the We consider the case where G is list-colorable and determine the irreducible of the remainder polynomial (or stipulation polynomial) 1c = fa mod J. We establish a bijection between the factors of and the edges of G.