# Linear and 2-frugal choosability of graphs of small maximum average degree

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 {\it 2-frugal} (resp. {\it 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 {\it 2-frugally} (resp. {\it linearly}) {\it $L$-colourable} if for a given list assignment $L:V(G)\mapsto 2^{\mathbb N}$, there exists a 2-frugal (resp. linear) colouring $c$ of $G$ such that $c(v)\in L(v)$ for all $v\in V(G)$. If $G$ is 2-frugally (resp. linearly) $L$-list colourable for any list assignment such that $|L(v)|\ge k$ for all $v\inV(G)$, then $G$ is {\it 2-frugally} (resp. {\it linearly}) {\it $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 :
Rapport
[Research Report] RR-7213, INRIA. 2010

https://hal.inria.fr/inria-00459692
Contributeur : Nathann Cohen <>
Soumis le : mercredi 24 février 2010 - 17:00:51
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : jeudi 18 octobre 2012 - 15:45:47

### Fichier

RR-7213.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00459692, version 1

### Citation

Nathann Cohen, Frédéric Havet. Linear and 2-frugal choosability of graphs of small maximum average degree. [Research Report] RR-7213, INRIA. 2010. 〈inria-00459692〉

### Métriques

Consultations de la notice

## 411

Téléchargements de fichiers