Class Ⅰ graphs of nonnegative characteristic without special cycles

In this paper,we prove that every graph with maximum degree six that can be embedded in a surface of nonnegative characteristic is of Class Ⅰ if it does not contain a 5- or 6-cycle with a chord,which e...     

On total chromatic number of planar graphs without 4-cycles

Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.     

Packing coloring of Sierpiński-type graphs

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in \{1,\ldots ,k\}\), where each \(V_i\) is an i-packing. In this paper, we consider the packing chromatic number of several families of Sierpiński-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpiński graphs with base 3, we prove that it is unbounded in the families of Sierpiński graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpiński triangle graphs \(ST^n_3\) is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpiński graphs \(S^n_G\) with respect to all connected graphs G of order 4.     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger thanβhave different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

The Alon–Tarsi number of planar graphs revisited

This paper gives a simple proof of the result that every planar graph $G$ has Alon–Tarsi number at most 5, and has a matching $M$ such that $G-M$ has Alon–Tarsi number at most 4.     

Acyclic Edge Coloring of 1-planar Graphs without 4-cycles

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ’α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ’_α(G) ≤Δ+2.A1-planar graph is a graph that 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 without 4-cycles h...     

On the limit cycles of a quintic planar vector field

This paper concerns the number and distributions of limit cycles in a Z_2-equivariant quintic planar vector field.25 limit cycles are found in this special planar polynomial system and four different configurations of these limit cycles are also given by using the methods of the bifurcation theory and the qualitative analysis of the differential equation.It can be concluded that H(5)≥25=5~2, where H(5)is the Hilbert number for quintic polynomial systems.The results obtained are useful to study the weakened 16th Hilbert problem.     

Partitioning planar graphs: a?fast combinatorial approach for max-cut

The max-cut problem asks for partitioning the nodes V of a graph G=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. (IEEE Trans. Comput. 39(5):694–697, 1990) and that of Berman et al. (WADS, Lecture Notes in Computer Science, vol. 1663, pp. 25–36, Springer, Berlin, 1999). The running time of the former can be bounded by O(|V|^frac32log|V|)O(|V|^{frac{3}{2}}log|V|). The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the running time of O(|V|^frac32(log|V|)^frac32)a(|V|)O(|V|^{frac{3}{2}}(log|V|)^{frac{3}{2}})alpha(|V|), where α(|V|) is the inverse Ackermann function, it can solve large instances in practice.     

Injective (Δ + 1)-coloring of planar graphs with girth 6

A vertex coloring of a graph G is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number χ _i (G) of the colors required for an injective coloring of a graph G is clearly not less than the maximum degree Δ(G) of G. There exist planar graphs with girth g ≥ 6 and χ _i = Δ+1 for any Δ ≥ 2. We prove that every planar graph with Δ ≥ 18 and g ≥ 6 has χ _i ≤ Δ + 1.     

Existence of limit cycles in general planar piecewise linear systems of saddle–saddle dynamics

The existence and number of limit cycles in a class of general planar piecewise linear systems constituted by two linear subsystems with saddle–saddle dynamics are investigated. Using the Liénard-like canonical form with seven parameters, the parametric regions of the existence of limit cycles are given by constructing proper Poincaré maps. In particular, the existence of at least two limit cycles is proved and some parameter regions where two nested limit cycles exist are given.     

Limit cycles and global dynamics of planar piecewise linear refracting systems of focus–focus type

The limit cycle problem of planar piecewise linear refracting systems has been solved except the focus–focus (FF) type. Here we concern this remaining FF type, and prove that such systems have at most one limit cycle and have 14 topologically different global phase portraits.     

The number and stability of limit cycles for planar piecewise linear systems of node–saddle type

The objective of this paper is to study the number and stability of limit cycles for planar piecewise linear (PWL) systems of node–saddle type with two linear regions. Firstly, we give a thorough analysis of limit cycles for Liénard PWL systems of this type, proving one is the maximum number of limit cycles and obtaining necessary and sufficient conditions for the existence and stability of a unique limit cycle. These conditions can be easily verified directly according to the parameters in the systems, and play an important role in giving birth to two limit cycles for general PWL systems. In this step, the tool of a Bendixon-like theorem is successfully employed to derive the existence of a limit cycle. Secondly, making use of the results gained in the first step, we obtain parameter regions where the general PWL systems have at least one, at least two and no limit cycles respectively. In addition for the general PWL systems, some sufficient conditions are presented for the existence and stability of a unique one and exactly two limit cycles respectively. Finally, some numerical examples are given to illustrate the results and especially to show the existence and stability of two nested limit cycles.     

Characterization of graphs having extremal Randi? indices

The higher Randi? index R_t(G) of a simple graph G is defined as

     

On the number of limit cycles in general planar piecewise linear systems of node–node types

We investigate the existence and number of limit cycles in a class of general planar piecewise linear systems constituted by two linear subsystems with node–node dynamics. Using the Liénard-like canonical form with seven parameters, some sufficient and necessary conditions for the existence of limit cycles are given by studying the fixed points of proper Poincaré maps. In particular, we prove the existence of at least two nested limit cycles and describe some parameter regions where two limit cycles exist. The main results are applied to the PWL Morris–Lecar neural model to determine the existence and stability of the limit cycles.     

The second volume moment of the typical cell and higher moments of edge lengths of the spatial Poisson–Voronoi tessellation

This paper presents analytical results for higher moments of characteristics of a Voronoi tessellation generated by a homogeneous Poisson point process in the three-dimensional Euclidean space. The second moment of the volume of the typical cell as well as higher moments for the edge length distribution and the linear contact distribution are given. These characteristics are calculated analytically and presented in a unified form.     

The second volume moment of the typical cell and higher moments of edge lengths of the spatial Poisson–Voronoi tessellation

This paper presents analytical results for higher moments of characteristics of a Voronoi tessellation generated by a homogeneous Poisson point process in the three-dimensional Euclidean space. The second moment of the volume of the typical cell as well as higher moments for the edge length distribution and the linear contact distribution are given. These characteristics are calculated analytically and presented in a unified form.