Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles (Q2084793): Difference between revisions

This 24 paged article deals with the concept of multiple DP-coloring of planar graphs. Multiple DP-coloring is a generalization of multiple list coloring. The aim of this paper is to prove that planar graphs without \(3\)-cycles and normally adjacent \(4\)-cycles are \((7m, 2m)\)-DP-colorable for every integer \(m\). Besides the main theorem, there are seven definitions, \(19\) lemmas, and six corollaries discussed here. The paper is divided into \(4\) sections, namely, Introduction, Strongly extendable coloring of a subset, \((f,2m)\)-DP-colorable graphs, and Proof of theorem \(1\). The introduction section poses two open problems, of which one is attended by this paper. It also consists of the basic definitions, the statement of the main theorem, and one of its corollaries. The second and third sections prove altogether \(10\) lemmas in order to prove the main theorem. There are a few corollaries also proved in these sections. Moreover, the second section discusses the techniques used to prove the results. The section on Proof of Theorem \(1\) discusses the remaining \(9\) lemmas and a corollary and thus completes the proof. A \(b\)-fold coloring of a graph \(G\) is a mapping \(\varphi\) which assigns to each vertex \(v\), a set \(\varphi(v)\) of \(b\) colors so that adjacent vertices receive disjoint color sets. An \((a, b)\)-coloring of \(G\) is a \(b\)-fold coloring \(\varphi\) of \(G\) such that \(\varphi(v)\subseteq \{1, 2,\ldots, a\}\) for each vertex \(v\). The fractional chromatic number of \(G \) is \(\chi_f(G) = \inf \{\frac{a}{b}: G\) is \((a, b)\)-colorable\(\}\). An \(a\)-list assignment of \(G\) is a mapping \(L\) which assigns to each vertex \(v \) a set \(L(v)\) of \(a\) permissible colors. A \(b\)-fold \(L\)-coloring of \(G\) is a \(b\)-fold coloring \(\varphi\) of \(G\) such that \(\varphi(v) \subseteq L(v)\) for each vertex \(v\). We say \(G\) is \((a, b)\)-choosable if, for any \(a\)-list assignment \(L\) of \(G\), there is a \(b\)-fold \(L\)-coloring of \(G\). The choice number of \(G\) is \(ch(G) =\) min \(\{a : G\) is \((a, 1)\)-choosable\(\}\). The fractional choice number of \(G\) is \(ch_f(G) = \inf \{r: G\) is \((a, b)\)-choosable for some positive integers \(a, b\) with \(\frac{a}{b} = r\}\). The strong fractional choice number of \(G\), which is a refinement of \(ch(G)\), is \(ch_f^\ast(G) = \inf \{r: G\) is \((a, b)\)-choosable for all positive integers \(a, b\) with \(\frac{a}{b} \ge r\}\). For a graph \(G\) and another graph \(H\), let \(\mathscr{H} = (L, H)\) be its cover, where \(L: V(G) \to \mathrm{Pow}(V(H))\) is a function. An \(\mathscr{H}\)-coloring of \(G\) is a mapping \(\varphi: V(G) \to V(H)\) such that \(\varphi(v) \in L(v)\) and \(\{\varphi(v) : v \in V(G)\} \) is an independent set of \(H\). If for every \(f\)-cover \(\mathscr{H}\) of \(G\), there is an \(\mathscr{H}\)-coloring of \(G\), then we say \(G\) is DP-\(f\)-colorable. We say \(G \) is DP-\(k\)-colorable if \(G\) is DP-\(f\)-colorable for the constant mapping \(f\) with \(f(v) = k\) for all \(v\). The DP-chromatic number of \(G\) is defined as \(\chi_{\mathrm{DP}}(G) =\) min \(\{k : G\) is DP-\( k\)-colorable\(\}\). If \(f,g : V(G) \to \mathbb{N}\) are constant maps with \(g(v) = b\) and \(f(v) = a\) for all \(v \in V(G)\), then \((\mathscr{H}, g)\)-colorable is called \((\mathscr{H}, b)\)-colorable, and \((f, g)\)-DP-colorable is called \((a, b)\)-DP-colorable. The strong fractional DP-chromatic number \(\chi_{\mathrm{DP}}^{\ast\ast}(G) = \inf \{r : G \) is \((a, b)\)-DP-colorable for every \(\frac{a}{b} \ge r\}\). For any graph \(G\), \(ch_f(G) \le \chi_{\mathrm{DP}}^\ast(G)\) and \(ch_f^\ast(G) \le \chi_{\mathrm{DP}}^{\ast\ast}(G)\). Thus we have the relations, \(\chi_{\mathrm{DP}}^\ast(G) \le \chi_{\mathrm{DP}}(G)\) and \(\chi_{\mathrm{DP}}^{\ast\ast}(G) \ge \chi_{\mathrm{DP}}(G)+1\). The main theorem of this paper is given as follows: Let \(G\) be a triangle-free planar graph without normally adjacent \(C_4\). Then, \(G\) is \((7m, 2m)\)-DP-colorable for every integer \(m\). This paper mainly depends on the method of induction to prove the various results and each case is discussed separately with the help of diagrams, whenever necessary. It extends an elaborate study of the problem at hand.