Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable

Marthe Bonamy 1 Benjamin Lévêque 2 Alexandre Pinlou 3, 4
2 G-SCOP_OC - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
4 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : For planar graphs, we consider the problems of list edge coloring and list total coloring. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list $\Delta$-edge-colorable or list $(\Delta +1)$-total-colorable, respectively, where $\Delta$ is the maximum degree in the graph. It is already known that planar graphs with $\Delta \geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $\Delta \geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k (\forall 3 \leq k \leq 6)$ are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.131-146
Liste complète des métadonnées

https://hal.inria.fr/lirmm-01347027
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 17:08:10
Dernière modification le : jeudi 26 octobre 2017 - 13:44:08

Fichier

2586-9917-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : lirmm-01347027, version 2

Citation

Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou. Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.131-146. 〈lirmm-01347027v2〉

Partager

Métriques

Consultations de
la notice

170

Téléchargements du document

87