Planar graphs with 7 and no triangle adjacent to a C₄ are minimally edge and total choosable

zbMATH Open1336.05033arXiv1405.3422MaRDI QIDQ2808541FDOQ2808541

Alexandre Pinlou, Marthe Bonamy, Benjamin Lévêque

Publication date: 24 May 2016

Published in: Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Abstract: For planar graphs, we consider the problems of emph{list edge coloring} and emph{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 edge $Delta$-colorable or list total $(Delta+1)$-colorable, respectively, where $Delta$ is the maximum degree in the graph. It is already known that planar graphs with $Deltageq8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $Deltageq7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k$ ($forall3leqkleq6$) are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $Deltageq7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.

Full work available at URL: https://arxiv.org/abs/1405.3422

zbMATH Keywords

planar graphsedge coloringdischarging

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cited In (5)

• An AIMMS-based decision-making model for optimizing the intelligent stowage of export containers in a single bay
• Analysis of the clustering fusion algorithm for multi-band color image
• Total colorings-a survey
• The list edge coloring and list total coloring of planar graphs with maximum degree at least 7
• Planar graphs with maximum degree D at least 8 are (D+1)-edge-choosable

This page was built for publication: Planar graphs with \(\Delta \geq 7\) and no triangle adjacent to a \(C_{4}\) are minimally edge and total choosable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808541)