Planar graphs with Δ≥7 and no triangle adjacent to a C4 are minimally edge and total choosable
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou
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
Δ-edge-colorable or list
(Δ+1)-total-colorable, respectively, where
Δ is the maximum degree in the graph. It is already
known that planar graphs with Δ≥8 and no
triangle adjacent to a C4 are minimally edge
and total choosable (Li Xu 2011), and that planar graphs with
Δ≥7 and no triangle sharing a vertex with a
C4 or no triangle adjacent to a
Ck (∀3 ≤k
≤6) are minimally total colorable (Wang Wu 2011). We
strengthen here these results and prove that planar graphs with
Δ≥7 and no triangle adjacent to a
C4 are minimally edge and total choosable.
Full Text: PDF PostScript