Lower bounds on the sum choice number of a graph

Given a simple graph 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) for all v∈V, where L(v) is any assignment of f(v) colors to v. The sum choice numberχsc(G) of G is defined to be the minimum of...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2016-09, Vol.53, p.421-431
Main Authors: Harant, Jochen, Kemnitz, Arnfried
Format: Article
Language:English
Subjects:
coloring
Graph
sum choice number
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a simple graph 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) for all v∈V, where L(v) is any assignment of f(v) colors to v. The sum choice numberχsc(G) of G is defined to be the minimum of ∑v∈Vf(v) over all choice functions f of G. In this paper we provide several new lower bounds on χsc(G) in terms of subgraphs of G.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2016.05.036