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.

A proper edge coloring of a graph G without isolated edges is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The neighbor-distinguishing index of G is the minimum number ndi(G) of colors in a neighbor-distinguishing edge coloring of G. Zhang, Liu, and Wang in 2002 conjectured that if G is a connected graph of order at least 6. In this article, the conjecture is verified for planar graphs with maximum degree at least 12.

An adjacent vertex distinguishing edge coloring of a graph $$G$$ is a proper edge coloring of $$G$$ such that any pair of adjacent vertices admit different sets of colors. The minimum number of colors required for such a coloring of $$G$$ is denoted by $$\chi ^{\prime }_{a}(G)$$ . In this paper, we prove that if $$G$$ is a planar graph with girth at least 5 and $$G$$ is not a 5-cycle, then $$\chi ^{\prime }_{a}(G)\le \Delta +2$$ , where $$\Delta $$ is the maximum degree of $$G$$ . This confirms partially a conjecture in Zhang et al. (Appl Math Lett 15:623---626, 2002).

The preparation, characterization, fluorescence (FL) and electrochemiluminescence (ECL) of graphite-like carbon nitride nanoflake particles (g-C(3)N(4) NFPs) and nanoflake films (g-C(3)N(4) NFFs) have been reported. Highly water-dispersible g-C(3)N(4) NFPs with a height of ~5 to 35 nm and a lateral dimension of ~40 to 220 nm have been extracted from bulk g-C(3)N(4) materials by chemical oxidation. New, stable and defined g-C(3)N(4) NFFs can be easily obtained by drying NFPs on certain hydrophilic substrates such as glass or electrode surfaces. Both g-C(3)N(4) NFPs and g-C(3)N(4) NFFs have good FL activities, i.e. they can give strong blue light (435 nm) emission under UV light (365 nm) excitation. The as-prepared g-C(3)N(4) NFFs on a glassy carbon electrode exhibit strong non-surface state ECL activity in the presence of reductive-oxidative coreactants, including dissolved oxygen (O(2)), hydrogen peroxide (H(2)O(2)) and peroxydisulfate (S(2)O(8)(2-)) and give rise to blue light emission (435 nm), which is the same as the wavelength of FL. The non-surface state ECL mechanisms of the g-C(3)N(4) NFF-coreactant systems have been studied and discussed in detail.

The vertex arboricity v a ( G ) of a graph G is the minimum number of colors the vertices can be labeled so that each color class induces a forest. It was well-known that v a ( G ) ≤ 3 for every planar graph G . In this paper, we prove that v a ( G ) ≤ 2 if G is a planar graph without 7-cycles. This extends a result in [A. Raspaud, W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008) 1064–1075] that for each k ∈ { 3 , 4 , 5 , 6 } , planar graphs G without k -cycles have v a ( G ) ≤ 2 .

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices have distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of G is denoted by $\chi''_{a}(G)$ . In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of planar graphs G with large maximum degree Δ by showing that if Δ?14, then $\varDelta+1\leq \chi''_{a}(G)\leq \varDelta+2$ , and $\chi''_{a}(G)=\varDelta+2$ if and only if G contains two adjacent vertices of maximum degree.

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of G is denoted by χa′′( G ). In this paper, we prove that every planar graph G with Δ( G ) ≥ 11 has χa′′( G ) ≤ Δ( G ) + 3.

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.

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices have different sets of colors. The minimum number of colors needed for such a total coloring of G is denoted by ? a ? ( G ) . In this note, we show that ? a ? ( G ) ? 2 Δ for any graph G with maximum degree Δ ? 3 .