Vertex colouring edge weightings: A logarithmic upper bound on weight-choosability

Kasper Szabo Lyngsie, Liang Zhong*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

1 Downloads (Pure)

Abstract

A graph G is said to be (k, m)-choosable if for any assignment of k-element lists (formula presented) to the vertices (formula presented) and any assignment of m-element lists (formula presented) to the edges (formula presented) there exists a total weighting w: V (G) ∪ E(G) → R of G such that w(v) ∈ Lv for any vertex (formula presented) and (formula presented)) and furthermore, such that for any pair of adjacent vertices u, v, we have (formula presented) w(e), where E(u) and E(v) denote the edges incident to u and v respectively. In this paper we give an algorithmic proof showing that any graph G without isolated edges is (formula presented)-choosable, where ∆(G) denotes the maximum degree in G.

Original languageEnglish
Article numberP2.11
JournalElectronic Journal of Combinatorics
Volume28
Issue number2
Number of pages11
ISSN1097-1440
DOIs
Publication statusPublished - 2021

Bibliographical note

Funding Information:
∗Supported by The China Scholarship Council

Publisher Copyright:
© The authors. Released under the CC BY license (International 4.0).

Fingerprint

Dive into the research topics of 'Vertex colouring edge weightings: A logarithmic upper bound on weight-choosability'. Together they form a unique fingerprint.

Cite this