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 , 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.
Type de document :
Article dans une revue
Graphs and Combinatorics, Springer Verlag, 2011, 27 (6), pp.831--849
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00638460
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:28:31
Dernière modification le : mardi 25 octobre 2016 - 01:05:07

Fichier

linear-soumis.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de
la notice

137

Téléchargements du document

84