Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles
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.
- DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\)
- DP-coloring on planar graphs without given adjacent short cycles
- Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
- DP-4-colorability of planar graphs without adjacent cycles of given length
- Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable
- Choosability and fractional chromatic numbers
- Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
- Every planar graph is 1-defective \((9,2)\)-paintable
- Fractional DP-colorings of sparse graphs
- Multiple list colouring of planar graphs
- Multiple list colouring triangle free planar graphs
- Planar graphs are \(9/2\)-colorable
This page was built for publication: Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084793)
