Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree

Nathann Cohen 1 Frédéric Havet 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A proper vertex colouring of a graph G is 2-frugal (resp. linear) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph G is 2-frugally (resp. linearly) L-colourable if for a given list assignment L : V(G) → N, there exists a 2-frugal (resp. linear) colouring c of G such that c(v) ∈ L(v) for all v ∈ V (G). If G is 2-frugally (resp. linearly) L-list colourable for any list assignment such that |L(v)| ≥ k for all v ∈ V (G), then G is 2-frugally (resp. linearly) k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.
Document type :
Journal articles
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/inria-00638460
Contributor : Frederic Havet <>
Submitted on : Sunday, October 23, 2016 - 4:28:31 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM

File

linear-soumis.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00638460, version 1

Collections

Citation

Nathann Cohen, Frédéric Havet. Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree. Graphs and Combinatorics, Springer Verlag, 2011, 27 (6), pp.831--849. ⟨inria-00638460⟩

Share

Metrics

Record views

224

Files downloads

178