Planar graphs without normally adjacent short cycles (Q2144582)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Planar graphs without normally adjacent short cycles |
scientific article |
Statements
Planar graphs without normally adjacent short cycles (English)
0 references
14 June 2022
0 references
DP-coloring also called correspondence coloring was introduced by \textit{Z. Dvořák} and \textit{L. Postle} [J. Comb. Theory, Ser. B 129, 38--54 (2018; Zbl 1379.05034)] which is regarded as a generalization of list-coloring. Let $G$ be a simple graph and $L$ be a list assignment for $G$. For each vertex $v\in V(G)$, let $L_{v}= \{v\}\times L(v);$ for each edge $uv\in E(G)$, let $\mathcal M_{uv}$ be a matching between the sets $L_{u}$ and $L_{v}$, and let $\mathcal M:=\bigcup_{uv\in E(G)}\mathcal M_{uv}$. Then $\mathcal M$ is called a matching assignment. Let $\mathcal G$ be the class of plane graphs without triangles normally adjacent to $8^{-}$-cycles, without 4-cycles normally adjacent to $6^{-}$-cycles, and without normally adjacent 5-cycles. The authors obtain the following result. Theorem 1: Let $G\in\mathcal G$ and let $S$ be a set of vertices of $G$ such that $|S|\leq 1$ or $S$ consists of all vertices on a normal cycle of $G$. Let $\mathcal M$ be a 3-matching assignment for $G$ such that $\mathcal M$ is consistent on every closed walk of length three in $G$. If $|S|\leq 12$, then every $\mathcal M$-coloring $\phi$ of $G[S]$ can be extended to an $\mathcal M$-coloring of $G$. The following result is deduced. Theorem 2: Every graph in $\mathcal G$ is 3-choosable. Then every planar graph without $4$-, $6$-, $8$-cycles is $3$-choosable. Every planar graph without $4$-, $5$-, $7$-, $8$-cycles is $3$-choosable. In addition, an $IF$-coloring of a graph $G$ is a partition of $V(G)$ into two parts $I$ and $F$, such that $G[I]$ is an independent set and $G[F]$ is a forest. The authors prove that every graph in $\mathcal G$ has an $IF$-coloring.
0 references
DP-coloring
0 references
near-bipartite
0 references
if-coloring
0 references
list coloring
0 references
0 references
0 references