Lower bounds on the sum choice number of a graph

详细信息    查看全文

• 作者：Jochen Harant ^{jochen.harant@tu-ilmenau.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph ; coloring ; sum choice number
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：53
• 期：Complete
• 页码：421-431
• 全文大小：227 K

文摘

Given a simple graph G=(V,E)$G=(V,E)$ and a function f from V to the positive integers, f is called a choice function of G if there is a proper vertex coloring ϕ   such that ϕ(v)∈L(v)$\varphi (v)\in L(v)$ for all i3" class="mathmlsrc">i3.gif&_user=111111111&_pii=S1571065316300907&_rdoc=1&_issn=15710653&md5=57ff9859709eec7dca4e11d01fdb64f8" title="Click to view the MathML source">v∈V, where L(v)$L(v)$ is any assignment of f(v)$f(v)$ colors to v. The sum choice number  χ_sc(G)${\chi }_{sc}(G)$ of G   is defined to be the minimum of ∑_v∈Vf(v)${\sum }_{v\in V}f(v)$ over all choice functions f of G  . In this paper we provide several new lower bounds on χ_sc(G)${\chi }_{sc}(G)$ in terms of subgraphs of G.