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
    0 references
    0 references
    0 references
    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
    0 references
    DP-coloring
    0 references
    near-bipartite
    0 references
    if-coloring
    0 references
    list coloring
    0 references

    Identifiers