2-connected chordal graphs and line graphs are (1, 5)-choosable. (January 2021)

• Record Type: Journal Article
• Authors: Wong, Tsai-Lien
• Is Part Of: European journal of combinatorics. Volume 91(2021)
• Publication Date: 2021-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103227
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Suppose G is a graph and k, k ′ are positive integers. A ( k, k ′ ) -list assignment is a mapping 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. A proper L -total weighting is a mapping ϕ : 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 u v . A graph G is called ( k, k ′ ) -choosable if for every ( k, k ′ ) -total list assignment L, there is a proper L -total weighting. This paper proves that chordal graphs with no cut-vertex are ( 1, 5 ) -choosable and line graphs are ( 1, 5 ) -choosable.