Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDP-3-coloring of planar graphs without certain cycles
120
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
DP-coloring is a generalization of list coloring, which was introduced by Dvov{r}{a}k and Postle [J. Combin. Theory Ser. B 129 (2018) 38--54]. Zhang [Inform. Process. Lett. 113 (9) (2013) 354--356] showed that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is 3-choosable. Liu et al. [Discrete Math. 342 (2019) 178--189] showed that every planar graph without 4-, 5-, 6- and 9-cycles is DP-3-colorable. In this paper, we show that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is DP-3-colorable, which generalizes these results. Yu et al. gave three Bordeaux-type results by showing that (i) every planar graph with the distance of triangles at least three and no 4-, 5-cycles is DP-3-colorable; (ii) every planar graph with the distance of triangles at least two and no 4-, 5-, 6-cycles is DP-3-colorable; (iii) every planar graph with the distance of triangles at least two and no 5-, 6-, 7-cycles is DP-3-colorable. We also give two Bordeaux-type results in the last section: (i) every plane graph with neither 5-, 6-, 8-cycles nor triangles at distance less than two is DP-3-colorable; (ii) every plane graph with neither 4-, 5-, 7-cycles nor triangles at distance less than two is DP-3-colorable.
rate research
Read More
Let $mathscr{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. In this paper, it is showed that every graph in $mathscr{G}$ is $3$-choosable. Instead of proving this result, we directly prove a stronger result in the form of weakly DP-$3$-coloring. The main theorem improves the results in [J. Combin. Theory Ser. B 129 (2018) 38--54; European J. Combin. 82 (2019) 102995]. Consequently, every planar graph without $4$-, $6$-, $8$-cycles is $3$-choosable, and every planar graph without $4$-, $5$-, $7$-, $8$-cycles is $3$-choosable. In the third section, it is proved that the vertex set of every graph in $mathscr{G}$ can be partitioned into an independent set and a set that induces a forest, which strengthens the result in [Discrete Appl. Math. 284 (2020) 626--630]. In the final section, tightness is considered.
In 1976, Steinberg conjectured that planar graphs without $4$-cycles and $5$-cycles are $3$-colorable. This conjecture attracted numerous researchers for about 40 years, until it was recently disproved by Cohen-Addad et al. (2017). However, coloring planar graphs with restrictions on cycle lengths is still an active area of research, and the interest in this particular graph class remains. Let $G$ be a planar graph without $4$-cycles and $5$-cycles. For integers $d_1$ and $d_2$ satisfying $d_1+d_2geq8$ and $d_2geq d_1geq 2$, it is known that $V(G)$ can be partitioned into two sets $V_1$ and $V_2$, where each $V_i$ induces a graph with maximum degree at most $d_i$. Since Steinbergs Conjecture is false, a partition of $V(G)$ into two sets, where one induces an empty graph and the other induces a forest is not guaranteed. Our main theorem is at the intersection of the two aforementioned research directions. We prove that $V(G)$ can be partitioned into two sets $V_1$ and $V_2$, where $V_1$ induces a forest with maximum degree at most $3$ and $V_2$ induces a forest with maximum degree at most $4$; this is both a relaxation of Steinbergs conjecture and a strengthening of results by Sittitrai and Nakprasit (2019) in a much stronger form.
The textit{$k$-weak-dynamic number} of a graph $G$ is the smallest number of colors we need to color the vertices of $G$ in such a way that each vertex $v$ of degree $d(v)$ sees at least $rm{min}{k,d(v)}$ colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.
It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on $t$ vertices, for fixed $t$. We propose an algorithm that, given a 3-colorable graph without an induced path on $t$ vertices, computes a coloring with $max{5,2lceil{frac{t-1}{2}}rceil-2}$ many colors. If the input graph is triangle-free, we only need $max{4,lceil{frac{t-1}{2}}rceil+1}$ many colors. The running time of our algorithm is $O((3^{t-2}+t^2)m+n)$ if the input graph has $n$ vertices and $m$ edges.
For nonnegative integers $k, d_1, ldots, d_k$, a graph is $(d_1, ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ parts so that the $i$th part induces a graph with maximum degree at most $d_i$ for all $iin{1, ldots, k}$. A class $mathcal C$ of graphs is {it balanced $k$-partitionable} and {it unbalanced $k$-partitionable} if there exists a nonnegative integer $D$ such that all graphs in $mathcal C$ are $(D, ldots, D)$-colorable and $(0, ldots, 0, D)$-colorable, respectively, where the tuple has length $k$. A set $X$ of cycles is a {it cycle obstruction set} of a class $mathcal C$ of planar graphs if every planar graph containing none of the cycles in $X$ as a subgraph belongs to $mathcal C$. This paper characterizes all cycle obstruction sets of planar graphs to be balanced $k$-partitionable and unbalanced $k$-partitionable for all $k$; namely, we identify all inclusion-wise minimal cycle obstruction sets for all $k$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
