Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Graphs and Combinatorics Année : 2011

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

Résumé

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.
Fichier principal
Vignette du fichier
linear-soumis.pdf (225.03 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00638460 , version 1 (23-10-2016)

Identifiants

  • HAL Id : inria-00638460 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More