Search

G has a list k-L(2, 1)-labeling if for any k-list assignment L, there exists a coloring $$c:V(G)\rightarrow \bigcup \limits _{v\in V} L(v)$$ of G such that $$c(v)\in L(v)$$ for $$\forall v\in V(G)$$ and for $$\forall u,v\in V(G)$$ , $$|c(u)-c(v)|\ge 2$$ if $$d(u,v)=1$$ , $$|c(u)-c(v)|\ge 1$$ if $$d(u,v)=2$$ . $$\lambda _{2,1}^{l}(G)=\min \{k|G$$ has a list k-L(2, 1)-labeling $$\}$$ is called the list L(2, 1)-labeling number of G. In this paper, we prove that for planar graph with maximum degree $$\Delta \ge 5$$ , girth $$g\ge 13$$ and without adjacent 13-cycles, $$\lambda _{2,1}^{l}(G)\le \Delta +3$$ holds. Moreover, the upper bound $$\Delta +3$$ is tight.

A graph G on n vertices is called non-universal if its maximum degree is at most $$n-2$$ . In this paper, we give a structural characterization for non-universal maximal planar graphs with diameter two. In precise, we find 10 basic graphs, and then generate all 25 non-universal maximal planar graphs with diameter two by adding repeatedly and appropriately 3-vertices to some of these 10 basic graphs. As an application, we show that maximal planar graphs with diameter two are pancyclic except five special graphs.

The adjacent vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that the edge coloring set on any pair of adjacent vertices is distinct. The minimum number of colors required for an adjacent vertex distinguishing edge coloring of G is denoted by $$\chi _{a}'(G)$$. It is observed that $$\chi _a'(G)\ge \Delta (G)+1$$ when G contains two adjacent vertices of degree $$\Delta (G)$$. In this paper, we prove that if G is a planar graph without 4-cycles, then $$\chi _a'(G)\le \max \{9,\Delta (G)+1\}$$.

A graph G is k -choosable if G can be properly colored whenever every vertex has a list of at least k available colors. In this paper, we will proof that if every 5-cycle of toroidal graph G is not adjacent simultaneously to 3-cycles and 4-cycles, then G is 4-choosable. This improves a result shown in Xu and Wu (2017), which stated that if every 5-cycle of planar graph G is not adjacent simultaneously to 3-cycles and 4-cycles, then G is 4-choosable.

The neighbor-distinguishing total coloring of a graph G is a proper total coloring of G using k colors such that any two adjacent vertices have different sets of colors. It was known that every planar graph G with $$\Delta \ge 10$$ is neighbor-distinguishing totally $$(\Delta +3)$$-colorable. In this paper, we extend this result to the case $$\Delta =9$$. Namely, we prove that every planar graph G with $$\Delta =9$$ is neighbor-distinguishing totally 12-colorable.

A graph G is k -choosable if it can be colored whenever every vertex has a list of at least k available colors. In this paper, we prove that every planar graph without chordal 6-cycles is 4-choosable. This extends a known result that every planar graph without 6-cycles is 4-choosable.

DP-coloring (also known as correspondence coloring) introduced by Dvor̆ák and Postle (2015) is a generalization of list coloring. In 2019, Chen et al. showed that planar graphs without [Formula: see text]-cycles adjacent to [Formula: see text]-cycles are DP-[Formula: see text]-colorable for [Formula: see text] and [Formula: see text]. In this paper, we will prove that planar graphs without [Formula: see text]-cycles adjacent simultaneously to [Formula: see text]-cycles and [Formula: see text]-cycles are DP-[Formula: see text]-colorable, which is an extension of the above result.

Given a graph G, we study the problem of finding the minimum number of colors required for a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets consisting of colors of their incident edges. This minimum number is called the 2-distance vertex-distinguishing index, denoted by $$\chi '_{d2}(G)$$?d2?(G). Using the breadth first search method, this paper provides a polynomial-time algorithm producing nearly-optimal solution in outerplanar graphs. More precisely, if G is an outerplanar graph with maximum degree $$\varDelta $$Δ, then the produced solution uses colors at most $$\varDelta +8$$Δ+8. Since $$\chi '_{d2}(G)\ge \varDelta $$?d2?(G)?Δ for any graph G, our solution is within eight colors from optimal.

The adjacent vertex distinguishing edge coloring of a graph [Formula: see text] is a proper edge coloring of [Formula: see text] such that the color sets of any pair of adjacent vertices are distinct. The minimum number of colors required for an adjacent vertex distinguishing edge coloring of [Formula: see text] is denoted by [Formula: see text]. It is observed that [Formula: see text] when [Formula: see text] contains two adjacent vertices of degree [Formula: see text]. In this paper, we prove that if [Formula: see text] is a planar graph without 3-cycles, then [Formula: see text]. Furthermore, we characterize the adjacent vertex distinguishing chromatic index for planar graphs of [Formula: see text] and without 3-cycles. This improves a result from [D. Huang, Z. Miao and W. Wang, Adjacent vertex distinguishing indices of planar graphs without 3-cycles, Discrete Math. 338 (2015) 139–148] that established [Formula: see text] for planar graphs without 3-cycles.

Let G = ( V , E ) be a graph. A ( Δ d 1 , Δ d 2 ) -partition of a graph G is the partition of V(G) into two non-empty subsets V1 and V2, such that G[V1] and G[V2] are graphs with maximum degree at most d1 and d2, respectively. A similar definition can be given for the notation ( F d 1 , F d 2 ) -partition if G[V1] and G[V2] are forests with maximum degree at most d1 and d2, respectively. For any d1 and d2, Montassier and Ochem constructed graphs with girth 4 which do not admit ( Δ d 1 , Δ d 2 ) -partition. In this paper, we show that planar graphs with girth at least 5 and without adjacent 5-cycles admit ( F 3 , F 3 ) -partition.

Let G be a maximal plane graph of diameter at most two. Let χl(G) and χd(G) denote the list chromatic number and the diagonal chromatic number of G, respectively. In this paper, we study the structure of G and show the following results: (1) χl(G) ≤ 4; and (2) χd(G) ≤ 9, and χ d ( G ) = 9 if and only if G is a specific graph on nine vertices.

Given a proper edge k -coloring ? and a vertex v ? V ( G ) , let C ? ( v ) denote the set of colors used on edges incident to v with respect to ? . The adjacent vertex distinguishing index of G , denoted by ? a ' ( G ) , is the least value of k such that G has a proper edge k -coloring which satisfies C ? ( u ) ? C ? ( v ) for any pair of adjacent vertices u and v . In this paper, we show that if G is a connected planar graph with maximum degree Δ ? 12 and without 3-cycles, then Δ ? ? a ' ( G ) ? Δ + 1 , and ? a ' ( G ) = Δ + 1 if and only if G contains two adjacent vertices of maximum degree. This extends a result in Edwards et?al. (2006), which says that if G is a connected bipartite planar graph with Δ ? 12 then ? a ' ( G ) ? Δ + 1 .

An adjacent vertex distinguishing coloring of a graph $G$ is a proper edge coloring of $G$ such that any pair of adjacent vertices admits different sets of colors. The minimum number of colors needed for such a coloring of $G$ is denoted by $\chi'_a(G)$. In this paper, we show that if $G$ is a planar graph with maximum degree $\Delta\ge 16$, then $\Delta\le \chi'_{a}(G)\le \Delta+1$, and $\chi'_a(G)=\Delta+1$ if and only if $G$ contains two adjacent vertices of maximum degree.

The 2-distance vertex-distinguishing index $$\chi '_{d2}G$$i¾?d2'G of a graph G is the least number of colors required for a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets of colors on their incident edges. Let G be a bipartite outerplanar graph of order n with maximum degree $$\varDelta $$Δ. We give an algorithm of time complexity $$On^3$$On3 to show that $$\chi '_{d2}G \le \varDelta +2$$i¾?d2'G≤Δ+2.