Search

Tutte's 3-flow conjecture states that every 4-edge-connected graph admits a nowhere-zero 3-flow. The planar case of Tutte's 3-flow conjecture is the classical Grotzsch's Theorem (1959). Steinberg and Younger (1989) further verified Tutte's 3-flow conjecture for projective planar graphs . In this paper we confirm Tutte's 3-flow conjecture for all toroidal graphs.

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.

A 1-planar graph is a graph that can be drawn in the Euclidean plane such that each edge crosses at most one edge. An independent crossing (IC)-planar graph is a 1-planar graph satisfying the condi...

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycle. A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In 2001, Borodin, Kostochka, Raspaud, and Sopena proved that every 1-planar graph is acyclically 20-colorable. In this paper, we improve this result by reducing 20 to 18.

The vertex-arboricity a(G) of a graph G is the minimum number of colors required for a vertex coloring of G such that no cycle is monochromatic. The list vertex-arboricity al(G) is the list-coloring version of this concept. In this paper, we prove that every planar graph G without intersecting 5-cycles has al(G) ≤ 2. This extends a result by Raspaud and Wang [On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008), 1064-1075] that every planar graph G without 5-cycles has a(G) ≤ 2.

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\}$$.

The neighbor-distinguishing total chromatic number $$\chi ''_{a}(G)$$ of a graph G is the minimum number of colors required for a proper total coloring of G such that any two adjacent vertices have different sets of colors. In this paper, we show that if G is a planar graph with $$\Delta =12$$, then $$13\le \chi ''_{a}(G)\le 14$$, and moreover $$\chi ''_{a}(G)=14$$ if and only if G contains two adjacent 12-vertices.

The linear 2-arboricity la 2 ( G ) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, we show that every 1-planar graph G of minimum degree at least 2 contains either a 29-light-edge or a 2-alternating-cycle. This result is applied to show that if the maximum degree of a 1-planar graph G is Δ , then la 2 ( G ) ≤ ⌈ Δ + 1 2 ⌉ + 14 . Since la 2 ( G ) ≥ ⌈ Δ 2 ⌉ for any graph G , our solution is within 14 from optimal.

The neighbor-distinguishing total chromatic number χ a ′ ′ ( G ) of a graph G is the smallest integer k such that G can be totally colored using k colors with a condition that any two adjacent vertices have different sets of colors. In this paper, we give a sufficient and necessary condition for a planar graph G with maximum degree 13 to have χ a ′ ′ ( G ) = 14 or χ a ′ ′ ( G ) = 15 . Precisely, we show that if G is a planar graph of maximum degree 13, then 14 ≤ χ a ′ ′ ( G ) ≤ 15 ; and χ a ′ ′ ( G ) = 15 if and only if G contains two adjacent 13-vertices.

The star chromatic index χ st ′ ( G ) of a graph G is the smallest integer k for which G has a proper edge k-coloring without bichromatic paths or cycles of length four. The strong chromatic index χ s ′ ( G ) of G is the smallest integer k for which G has a proper edge k-coloring such that any two edges at distance at most two get distinct colors. In this paper, we prove that if a graph G can be edge-partitioned into two graphs F and H, then χ st ′ ( G ) ≤ χ st ′ ( F ) + χ s ′ ( H | G ) , where χ s ′ ( H | G ) denotes the strong chromatic index of H restricted on G. Using this result, we give some upper bounds of the star chromatic index for planar graphs. Precisely, we show that (1) if G is a planar graph with maximum degree Δ, then χ st ′ ( G ) ≤ 2.75 Δ + 18 ; (2) if G is a planar graph without 4-cycles, then χ st ′ ( G ) ≤ ⌊ 1.5 Δ ⌋ + 18 ; (3) if G is a planar graph of girth at least 8, then χ st ′ ( G ) ≤ ⌊ 1.5 Δ ⌋ + 3 ; (4) if G is a K4-minor free graph, then χ st ′ ( G ) ≤ 2.25 Δ + 6 ; and (5) if G is an outerplanar graph, then χ st ′ ( G ) ≤ ⌊ 1.5 Δ ⌋ + 5 , which improves a result in Bezegova et al. [2], which says that χ st ′ ( G ) ≤ ⌊ 1.5 Δ ⌋ + 12 for an outerplanar graph G.

A bridgeless graph G is called 3-flow-critical if it does not admit a nowhere-zero 3-flow, but G / e has one for any e ∈ E ( G ) . Tutte’s 3-flow conjecture can be equivalently stated as that every 3-flow-critical graph contains a vertex of degree three. In this paper, we study the structure and extreme size of 3-flow-critical graphs. We apply structural properties to obtain lower and upper bounds on the size of 3-flow-critical graphs, that is, for any 3-flow-critical graph G on n vertices, 8 n − 2 5 ≤ | E ( G ) | ≤ 4 n − 10 , where each equality holds if and only if G is K 4 . We conjecture that every 3-flow-critical graph on n ≥ 7 vertices has at most 3 n − 8 edges, which would be tight if true. For planar graphs, the best possible upper bound for the size of 3-flow-critical graphs on n vertices is 5 n − 8 2 , known from a result of Kostochka and Yancey (2014) on vertex coloring 4-critical graphs by duality.

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.

Given a graph G = ( V , E ) , if its vertex set V(G) can be partitioned into two non-empty subsets V1 and V2 such that G[V1] is edgeless and G[V2] is a graph with maximum degree at most k, then we say that G admits an (I, Δk)-partition. A similar definition can be given for the notation (I, Fk)-partition if G[V2] is a forest with maximum degree at most k. The maximum average degree of G is defined to be mad ( G ) = max { 2 | E ( H ) | | V ( H ) | : H ⊆ G } . Borodin and Kostochka (2014) proved that every graph G with mad ( G ) ≤ 8 3 admits an (I, Δ2)-partition and every graph G with mad ( G ) ≤ 14 5 admits an (I, Δ4)-partition. In this paper, we obtain a strengthening result by showing that for any k ≥ 2, every graph G with mad ( G ) ≤ 2 + k k + 1 admits an (I, Fk)-partition. As a corollary, every planar graph with girth at least 7 admits an (I, F4)-partition and every planar graph with girth at least 8 admits an (I, F2)-partition. The later result is best possible since neither girth condition nor the class of F2 can be further improved.

A strong edge-coloring of a graph is a proper edge-coloring such that edges at distance at most 2 receive different colors. It is known that every planar graph has a strong edge-coloring by using at most 4 Δ + 4 colors, where Δ denotes the maximum degree of the graph. In this paper, we will show that 19 colors are enough to color a planar graph with maximum degree 4.

Let G be a connected graph with \(n\ge 2\) vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each step, the firefighter protects two vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn\(_2(v)\) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The 2-surviving rate \(\rho _2(G)\) of G is defined to be the real number \(\frac{1}{n^2} \sum _{v\in V(G)} \mathrm{sn}_2(v)\). Then it is obvious that \(0 0\) such that \(\rho _2(G)>c\). In this paper, we prove that every planar graph with \(n\ge 2\) vertices and without chordal 5-cycles is 2-good.

The entire chromatic number χ vef ( G ) of a plane graph G is the least number of colors such that any two adjacent or incident elements in V ( G ) ∪ E ( G ) ∪ F ( G ) receive different colors. In this paper, we prove that every 2-connected simple plane graph G with maximum degree Δ ≥ 20 has χ vef ( G ) = Δ + 1 .

The linear 2-arboricity la2(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose components are paths of length at most 2. In this paper, we prove that every planar graph G with =10 has la2(G)9. Using this result, we correct an error in the proof of a result in Wang (2016), which says that every planar graph G satisfies la2(G)(+1)2+6.

A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying \(|L(x)\cap L(y)|\le d\) for each edge xy. An L-coloring is a vertex coloring \(\pi \) such that \(\pi (v) \in L(v)\) for each vertex v and \(\pi (x) \ne \pi (y)\) for each edge xy. A graph G is (k, d)-choosable if there exists an L-coloring of G for every (k, d)-list assignment L. This concept is known as choosability with separation. In this paper, we will use Thomassen list coloring extension method to prove that planar graphs with neither 6-cycles nor adjacent 4- and 5-cycles are (3, 1)-choosable. This is a strengthening of a result obtained by using Discharging method which says that planar graphs without 5- and 6-cycles are (3, 1)-choosable.

The vertex-arboricity a ( G ) of a graph G is the minimum number of colors required to color the vertices of G such that no cycle is monochromatic. The list vertex-arboricity a l ( G ) is the list-coloring version of this concept. Kronk and Mitchem (1975) proved that every toroidal graph G without 3 -cycles has a ( G ) ź 2 . Choi and Zhang (2014) proved that every toroidal graph G without 4 -cycles has a ( G ) ź 2 . Borodin and Ivanova (2009) proved that every planar graph G without 4 -cycles adjacent to 3 -cycles has a l ( G ) ź 2 . In this paper, we improve and extend these results by showing that a l ( G ) ź 2 if G is a toroidal graph without adjacent 3- and 4-cycles.

A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying $$|L(x)\cap L(y)|\le d$$ for each edge xy. An L-coloring is a vertex coloring $$\pi $$ such that $$\pi (v) \in L(v)$$ for each vertex v and $$\pi (x) \ne \pi (y)$$ for each edge xy. A graph G is (k, d)-choosable if there exists an L-coloring of G for every (k, d)-list assignment L. This concept is known as choosability with separation. In this paper, we prove that planar graphs without 4-cycles adjacent to $$4^-$$ -cycles are (3, 1)-choosable. This is a strengthening of a result which says that planar graphs without 4-cycles are (3, 1)-choosable.

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.

In terms of constraining the list assignment, one refinement of k-choosability is considered as choosability with separation. We call a graph (k, d)-choosable if it is colorable from lists of size k where adjacent vertices have at most d common colors in their lists. If two cycles have exactly one common edge, then they are said to be normally adjacent. In this article, it is shown that planar graphs without 5-cycles and normally adjacent 4-cycles are (3,1)-choosable. This extends a result that planar graphs without 5- and 6-cycles are (3,1)-choosable (Choi et al. (2016))

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.

A graph G is called an IC-planar graph if it can be embedded in the plane so that every edge is crossed by at most one other edge and every vertex is incident to at most one crossing edge. In this paper, we prove that every IC-planar graph is acyclically 10-colorable. Moreover, an IC-planar graph of the acyclic chromatic number 6 is constructed.

A list assignment of a graph G is a function L that assigns a list L(v) of colors to each vertex $$v\in V(G)$$vźV(G). An $$(L,d)^*$$(L,d)ź-coloring is a mapping $$\pi $$ź that assigns a color $$\pi (v)\in L(v)$$ź(v)źL(v) to each vertex $$v\in V(G)$$vźV(G) so that at most d neighbors of v receive color $$\pi (v)$$ź(v). A graph G is said to be $$(k,d)^*$$(k,d)ź-choosable if it admits an $$(L,d)^*$$(L,d)ź-coloring for every list assignment L with $$|L(v)|\ge k$$|L(v)|źk for all $$v\in V(G)$$vźV(G). In this paper, we prove that every planar graph with neither adjacent triangles nor 6-cycles is $$(3,1)^*$$(3,1)ź-choosable. This is a partial answer to a question of Xu and Zhang (Discret Appl Math 155:74---78, 2007) that every planar graph without adjacent triangles is $$(3,1)^*$$(3,1)ź-choosable. Also, this improves a result in Lih et al. (Appl Math Lett 14:269---273, 2001) which says that every planar graph without 4- and 6-cycles is $$(3,1)^*$$(3,1)ź-choosable.

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 .

Let $$G$$G be a connected graph with $$n\ge 2$$n?2 vertices. Let $$k\ge 1$$k?1 be an integer. Suppose that a fire breaks out at a vertex $$v$$v of $$G$$G. A firefighter starts to protect vertices. At each step, the firefighter protects $$k$$k-vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let $$\hbox {sn}_k(v)$$snk(v) denote the maximum number of vertices in $$G$$G that the firefighter can save when a fire breaks out at vertex $$v$$v. The $$k$$k-surviving rate $$\rho _k(G)$$?k(G) of $$G$$G is defined to be $$\frac{1}{n^2}\sum _{v\in V(G)} {\hbox {sn}}_{k}(v)$$1n2?v?V(G)snk(v), which is the average proportion of saved vertices. In this paper, we prove that if $$G$$G is a planar graph with $$n\ge 2$$n?2 vertices and without 5-cycles, then $$\rho _2(G)>\frac{1}{363}$$?2(G)>1363.

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 plane graph $$G$$G is entirely $$k$$k-choosable if, for every list $$L$$L of colors satisfying $$L(x)=k$$L(x)=k for all $$x\in V(G)\cup E(G) \cup F(G)$$x?V(G)?E(G)?F(G), there exists a coloring which assigns to each vertex, each edge and each face a color from its list so that any adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph $$G$$G with maximum degree $$\Delta \ge 12$$Δ?12 is entirely $$(\Delta +2)$$(Δ+2)-choosable. In this paper, we improve this result by replacing 12 by 10.

Let G@? be a connected digraph with n>=2 vertices. Suppose that a fire breaks out at a vertex v of G@?. A firefighter starts to protect vertices. At each time interval, the firefighter protects k vertices not yet on fire. Afterward, the fire spreads to all unprotected neighbors that are heads of some arcs starting from the vertices on fire. Let sn"k(v) denote the maximum number of vertices in G@? that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate @r"k(G@?) of G@? is defined as @?"v"@?"V"("G"@?")sn"k(v)/n^2. In this paper, we consider the k-surviving rate of digraphs. Main results are as follows: (1) if G@? is a k-degenerate digraph, then @r"k(G@?)>=1k+1; (2) if G@? is a planar digraph, then @r"2(G@?)>140; (3) if G@? is a planar digraph without 4-cycles, then @r"1(G@?)>151.

The firefighter problem models the spread of a fire or virus through a network and the k-surviving rate of G, @r"k(G), is the expected proportion of nodes k fire fighters per turn can save. In this paper, we show that if G is a planar graph with at least two vertices and having no 6-cycles, then @r"2(G)>185.

A plane graph $G$ is entirely $k$-colorable if $V(G)\cup E(G) \cup F(G)$ can be colored with $k$ colors such that any two adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph $G$ with maximum degree $\Delta\ge 12$ is entirely $(\Delta+2)$-colorable. In this paper, we improve this result by showing that every plane graph $G$ with $\Delta\ge 9$ is entirely $(\Delta+2)$-colorable.

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles. Given a list assignment L = {L(v) | v ∈ V} of G, we say that G is acyclically L-colorable if there exists a proper acyclic coloring π of G such that π(v) ∈ L(v) for all v ∈ V. If G is acyclically L-colorable for any list assignment L with |L(v)| ⩾ k for all v ∈ V (G), then G is acyclically k-choosable. In this paper, we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i ∈ {3, 4, 5, 6}. This improves the result by Wang and Chen (2009).

The vertex arboricity va G of a graph G is the minimum number of colours the vertices can be coloured so that each colour class induces a forest. It was known that va G ≤3 for every planar graph G , and the problem of computing vertex arboricity of graphs is NP-hard. In this paper, we prove that va G ≤2 if G is a planar graph without chordal 6-cycles. This extends a result by Raspaud and Wang [ On the vertex-arboricity of planar graphs , Eur. J. Combin. 29 2008, pp. 1064–1075].

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).

Let G be a connected graph with n>=2 vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects two vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn"2(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The surviving rate @r"2(G) of G is defined to be @?"v"@?"V"("G")sn"2(v)/n^2, which is the average proportion of saved vertices. In this paper, we show that if G is a planar graph with n>=2 vertices and without 4-cycles, then @r"2(G)>176.

Let G be a connected graph with n?2 vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects one vertex not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let sn(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The surviving rate ?(G) of G is defined to be ? v?V(G)sn(v)/n 2, which is the average proportion of saved vertices. In this paper, we show that if G is a planar graph with n?2 vertices and having girth at least 7, then $\rho(G)>\frac{1}{301}$ .

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.

The vertex-arboricity a(G) of a graph G is the minimum number of subsets into which vertex set V(G) can be partitioned so that each subset induces an acyclic graph. In this paper, we prove one of the conjectures proposed by Raspaud and Wang (2008) [15] which says that a(G)=2 for any planar graph without intersecting triangles.

Let G be a connected graph with n>=2 vertices. Let k>=1 be an integer. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects k-vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let sn"k(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate @r"k(G) of G is defined to be @?"v"@?"V"("G")sn"k(v)/n^2, which is the average proportion of saved vertices. In this paper, we show that every planar graph G with minimum degree @d satisfies @r"4(G)>311 if @d=5, @r"4(G)>319 if @d=4, and @r"4(G)>19 if @d@?3. This improves a result in [W. Wang, S. Finbow, P. Wang, The surviving rate of an infected network, Theoret. Comput. Sci. 411 (2010) 3651-3660].

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a^'(G) of G is the smallest k such that G has an acyclic edge coloring using k colors. In this paper, we prove that every planar graph G with girth g(G) and maximum degree @D has a^'(G)[email protected] if there exists a pair (k,m)@?{(3,11),(4,8),(5,7),(8,6)} such that G satisfies @D>=k and g(G)>=m.

A k-coloring of a graph G=(V,E) is a mapping c:V?{1,2,?,k}. The coloring c is injective if, for every vertex v?V, all the neighbors of v are assigned with distinct colors. The injective chromatic number ? i (G) of G is the smallest k such that G has an injective k-coloring. In this paper, we prove that every K 4-minor free graph G with maximum degree Δ?1 has $\chi_{i}(G)\le \lceil \frac{3}{2}\Delta\rceil$ . Moreover, some related results and open problems are given.

Let G be a connected network. Let k>=1 be an integer. Suppose that a vertex v of G becomes infected. A program is then installed on k-nodes not yet infected. Afterwards, the virus spreads to all its unprotected neighbors in each time interval. The virus and the network administrator take turns until the virus can no longer spread further. Let sn"k(v) denote the maximum number of vertices in G the network administrator can save when a virus infects v. The k-surviving rate @r"k(G) of G is defined to be the average value @?"v"@?"V"("G")sn"k(v)/n^2. In particular, we write @r(G)[email protected]"1(G). In this paper, we first use a probabilistic method to show that almost all networks have k-surviving rate arbitrarily close to 0. Then, we prove the following results: (1) @r(G)>=235 for a planar network G of girth at least 9; (2) @r"2(G)>=116 for a series-parallel network G; and (3) @r"""2"""d"""-"""1(G)>=25d for a d-degenerate network G.

A short cycle means a cycle of length at most 7. In this paper, we prove that planar graphs without adjacent short cycles are 3-colorable. This improves a result of Borodin et al. (2005).

Recently, Kowalik, Sereni, and Škrekovski proved that planar graphs with maximum degree 9 are 10-totally colorable. This work proves that planar graphs with maximum degree 8 and without intersecting triangles are 9-totally colorable.