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 {\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
Liste complète des métadonnées

https://hal.inria.fr/inria-00459692
Contributeur : Nathann Cohen <>
Soumis le : mercredi 24 février 2010 - 17:00:51
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
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〉

Partager

Métriques

Consultations de la notice

436

Téléchargements de fichiers

116