2015/10/03 by Tsai‐Lien Wong, Wong, Tsai-Lien, Xuding Zhu +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1510.00809
openalex publication_date 2015/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is (k,k')-choosable if the following holds: For any list assignment L which assigns to each vertex v a set L(v) of k real numbers, and assigns to each edge e a set L(e) of k' real numbers, there is a total weighting ϕ: V(G) ∪ E(G) → R such that ϕ(z) ∈ L(z) for z ∈ V ∪ E, and ∑e ∈ E(u)ϕ(e)+ϕ(u) ≠ ∑e ∈ E(v)ϕ(e)+ϕ(v) for every edge uv. This paper proves the following results: (1) If G is a connected d-degenerate graph, and k>d is a prime number, and G is either non-bipartite or has two non-adjacent vertices u,v with d(u)+d(v) < k, then G is (1,k)-choosable. As a consequence, every planar graph with no isolated edges is (1,7)-choosable, and every connected 2-degenerate non-bipartite graph other than K2 is (1,3)-choosable. (2) If d+1 is a prime number, v1, v2, …, vn is an ordering of the vertices of G such that each vertex vi has back degree d-(vi) ≤ d, then there is a graph G' obtained from G by adding at most d-d-(vi) leaf neighbours to vi (for each i) and G' is (1,2)-choosable. (3) If G is d-degenerate and d+1 a prime, then G is (d,2)-choosable. In particular, 2-degenerate graphs are (2,2)-choosable. (4) Every graph is (\lceil\frac\rm mad(G)2\rceil+1, 2) -choosable. In particular, planar graphs are (4,2)-choosable, planar bipartite graphs are (3,2)-choosable.