Bounding the monomial index and (1,l)-weight choosability of a graph
Ben Seamone
Abstract
Let G = (V,E) be a graph. For each e
∈E(G) and v ∈V(G), let
Le and Lv,
respectively, be a list of real numbers. Let w be a
function on V(G) ∪E(G) such that w(e)
∈Le for each e ∈E(G) and
w(v) ∈Lv for each v
∈V(G), and let cw be the vertex
colouring obtained by cw(v) = w(v) + ∑_e ∋vw(e). A graph is
(k,l)-weight choosable if there exists a weighting
function w for which cw is proper
whenever |Lv| ≥k and
|Le| ≥l for every v
∈V(G) and e ∈E(G). A sufficient
condition for a graph to be (1,l)-weight choosable was
developed by Bartnicki, Grytczuk and Niwczyk (2009), based on the
Combinatorial Nullstellensatz, a parameter which they call the
monomial index of a graph, and matrix permanents. This paper extends
their method to establish the first general upper bound on the
monomial index of a graph, and thus to obtain an upper bound on
l for which every admissible graph is
(1,l)-weight choosable. Let
∂2(G) denote the smallest value
s such that every induced subgraph of G has
vertices at distance 2 whose degrees sum to at most
s. We show that every admissible graph has monomial
index at most ∂2(G) and hence that
such graphs are (1, ∂2(G)+1)-weight
choosable. While this does not improve the best known result on
(1,l)-weight choosability, we show that the results can
be extended to obtain improved bounds for some graph products; for
instance, it is shown that G □ Kn is
(1, nd+3)-weight choosable if G is
d-degenerate.
Full Text: PDF PostScript