Total Weight Choosability of Graphs
The Electronic Journal of Combinatorics2011Vol. 18(1)
Citations Over TimeTop 10% of 2011 papers
Abstract
Suppose the edges and the vertices of a simple graph $G$ are assigned $k$-element lists of real weights. By choosing a representative of each list, we specify a vertex colouring, where for each vertex its colour is defined as the sum of the weights of its incident edges and the weight of the vertex itself. How long lists ensures a choice implying a proper vertex colouring for any graph? Is there any finite bound or maybe already lists of length two are sufficient? We prove that $2$-element lists are enough for trees, wheels, unicyclic and complete graphs, while the ones of length $3$ are sufficient for complete bipartite graphs. Our main tool is an algebraic theorem by Alon called Combinatorial Nullstellensatz.
Related Papers
- → Two sufficient conditions for a 2‐factor in a bipartite graph(1987)15 cited
- → The Biclique Cover Problem and the Modified Galois Lattice(2015)2 cited
- → On bipartite powers of bigraphs(2012)1 cited
- → Biclique: An R package for Maximal Biclique Enumeration in Bipartite Graphs(2019)1 cited
- → An Exact Algorithm for Finding <i>K</i>-Biclique Vertex Partitions of Bipartites(2013)