Ben Seamone - Bounding the monomial index and (1,l)-weight choosability of a graph

dmtcs:2097 - Discrete Mathematics & Theoretical Computer Science, September 17, 2014, Vol. 16 no. 3 -
Bounding the monomial index and (1,l)-weight choosability of a graph

Authors: Ben Seamone ORCID-iD1

  • 1 Département d'Informatique et de Recherche Opérationnelle [Montreal]

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) + ∑ₑ ∋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.

Volume: Vol. 16 no. 3
Section: Graph Theory
Published on: September 17, 2014
Submitted on: September 23, 2013
Keywords: 1-2-3 Conjecture,Combinatorial Nullstellensatz,permanents,graph colouring,graph labelling,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1611.03181
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.dam.2016.10.028
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1611.03181
  • 10.1016/j.dam.2016.10.028
  • 10.48550/arxiv.1611.03181
  • 1611.03181
On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs

Consultation statistics

This page has been seen 361 times.
This article's PDF has been downloaded 314 times.