Comparison of sum choice number with chromatic sum Artikel uri icon

Open Access

  • false

Peer Reviewed

  • true

Abstract

  • Let G = (V, E) be a simple graph and for every vertex v is an element of V let L(v) be a set (list) of available colors. The graph G is called L-colorable if there is a proper coloring yo of the vertices with phi(v) is an element of L(v) for all v is an element of V. A function f : V -> N is called a choice function of G if G is L-colorable for every list assignment L with vertical bar L(v)vertical bar = f (v) for all v is an element of V. Let size(f ) = Sigma(v is an element of V) f (v) and define the sum choice number chi(sc)(G) as the minimum of size(f ) over all choice functions f of G. The chromatic sum Sigma(G) of G is the minimum sum of colors taken over all possible proper colorings of G. In this paper we consider the functions g(n) = max{chi(sc )(G)/Sigma(G) : Sigma(G) = n} and h(n) = max{chi(sc)(G)/Sigma(G) : vertical bar V(G)vertical bar = n}. We conjecture g(n) = circle minus(logn), h(n) = circle minus(logn), and g(n) < h(n) for all n. We present lower and upper bounds for g(n) and h(n) and partial proofs of the conjectures. (C) 2021 Elsevier B.V. All rights reserved.

Veröffentlichungszeitpunkt

  • Januar 7, 2021