Originator(s): Garth Isaak (presented by West - REGS 2008)
Definitions: Let f be an assignment of positive integers to the vertices of a graph G. We say that G is f-choosable if whenever each vertex v is assigned a list L(v) of available colors, it is possible to choose c(v)∈L(v) for all v so that c is a proper coloring of G. The sum-list chromatic number or sum-choosability of G is the minimum value of ∑v∈V(G)f(v) such that G is f-choosable. We write s(G) for this parameter here.
Background: By putting the vertices in any order and giving each vertex a list whose size is one more than its number of earlier neighbors, it follows that always s(G) is at most the number of vertices plus the number of edges in G. Let b(G)=|V(G)|+|E(G)|, using "b" for "bound". In [BBBD], graphs for which s(G)=b(G) are called sum choice greedy, now simply sc-greedy. In general, one would like to characterize the sc-greedy graphs, but doing so seems hopelessly difficult, and instead we seek sufficient conditions for graphs to be sc-greedy or to be non-sc-greedy.
Comments: It is easy to prove that complete graphs are sc-greedy. Isaak [I2] extended this to block graphs, which are the graphs in which every block is a complete graph. More generally, [BBBD] proved that if every block of a graph G is sc-greedy, then G is sc-greedy. This is a corollary of their important result that if G=F∪H where F∩H=K1, then s(G)=s(F)+s(H)-1.
Cycles are easily shown to be sc-greedy. With a bit more effort, Heinold [H1] showed that theta graphs (union of three paths with common endpoints) are sc-greedy unless two of the paths have length 2 and the third has even length (this relies on the fact that these are the theta graphs that are 2-choosable -- note that K2,3 is a special case). Also the Petersen graph is sc-greedy [H1].
Heinold [H] extended the result on cycles by showing that every graph formed by pasting together cycles of length at least 4 at single edges (forming cut-sets of size 2) is sc-greedy. For example, this includes the 2-by-n grid that is the cartesian product of P2 and Pn.
Question 1: Under what conditions is it true that s(G∪H) = s(G)+s(H)-3 for graphs G and H with G∩H=K2?
Comments: Although pasting of non-triangular cycles is a sufficient condition in Question 1, not all pastings of G and H have this property. In particular, the join of a single vertex with Pn-1 (called the n-fan) is chordal, is outerplanar, and is obtained by pasting together triangles at edges. Nevertheless, it is not sc-greedy. Heinold [H1] showed that its sum choice number differs from the greedy bound by ⌊n/11⌋.
Question 2: The sc-gap of a graph G is b(G)-s(G). What is the maximum of the sc-graph for n-vertex graphs? For n-vertex outerplanar graphs? For n-vertex split graphs?
Comments: The sum choice number has been determined for several other families, which may shed light on these questions. The (distance) square of a path is sc-greedy [H1]. A grid with three rows and at least three columns is not; the sc-gap of the 3-by-n/3 grid is ⌊n/9⌋ [H1]. Isaak [I1] proved that the sum-choosability of the line graph L(K2,n) is n²+⌈5n/3⌉; what about L(K3,n)? ([BBBD] showed that s(L(K3,3))=25.
[BBBD] proved that s(K2,q)=2q+1+⌊√{4q+1}⌋; the sc-gap here is approximately asymptotic to the number of vertices. Also, Heinold [H1] showed that s(K3,q)=2q+1+⌊√{12q+4}⌋; here the sc-gap is approximately asymptotic to twice the number of vertices. It is reasonable to conjecture that Kn/2,n/2 may have the largest sc-gap among n-vertex graphs. Among n-vertex split graphs, it would be reasonable to study Kn/2∨K̅n/2.
The proofs of these computations provide some useful techniques. Heinold's thesis is available on his web page: http://faculty.msmary.edu/Heinold/ . Also, Heinold [H2] provides a short survey of sum list coloring. (Heinold was a student of Garth Isaak.)
Finally, we remark that one can divide the sum-choosability by the number of vertices to obtain an equivalent measure we might call the average-choosability. The upper bound on sum-choosability shows that the average-choosability is at most 1 plus half the average vertex degree; equality holds for cycles.
When k is a positive integer, a graph G is k-choosable if it is f-choosable for the function f that assigns k to every vertex. The choosability of G is the least integer k such that G is k-choosable. By definition, the average-choosability of a graph is at most its choosability. Are there graphs other than even cycles whose average choosability equals their choosability?
References:
[BBBD]
Berliner, Adam; Bostelmann, Ulrike; Brualdi, Richard A.; Deaett, Louis; Sum list
coloring graphs. Graphs Combin. 22 (2006), no. 2, 173--183.
[H1]
Heinold, Brian; Sum List Coloring and Choosability, PhD Thesis, Lehigh
University, 2006.
[H2]
Heinold, Brian; A survey of sum list coloring. Graph Theory Notes N. Y. 52
(2007), 38--44.
[I1]
Isaak, Garth; Sum list coloring 2×n arrays. Electron. J. Combin.
9 (2002), no. 1, Note 8, 7 pp.
[I2]
Isaak, Garth; Sum list coloring block graphs. Graphs Combin. 20 (2004), no.
4, 499--506.