Search

In 2020, the impact of the COVID-19 pandemic plunged the world into its worst economic crisis since 2008, and international trade was frustrated by the double whammy of escalating protectionism and the pandemic in recent years. Affected by the epidemic in 2020, many Chinese companies cannot sustain themselves, and the remaining enterprises are only barely maintaining the status quo and waiting for the epidemic to pass. During this period, the overall trend of the stock market fell sharply due to the epidemic, but due to the government's policies, it was still pulled up.

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.

This paper studies a robust equilibrium strategy for a mean-variance defined contribution (DC) pension plan with ambiguity aversion and return of premiums clauses in a jump-diffusion model. Ambigui...

In 1983, Bouchet proposed a conjecture that every flow-admissible signed graph admits a nowhere-zero 6-flow. Bouchet himself proved that such signed graphs admit nowhere-zero 216-flows and Zýka further proved that such signed graphs admit nowhere-zero 30-flows. In this paper we show that every flow-admissible signed graph admits a nowhere-zero 11-flow.

This paper studies the fundamental relations among integer flows, modulo orientations, integer-valued and real-valued circular flows, and monotonicity of flows in signed graphs. A (signed) graph is...

This paper consists of two major parts. In the first part, the relations between Tutte orientations and circular flows are explored. Tutte orientation (modulo orientation) was first observed by Tutte for the study of 3-flow problem, and later extended by Jaeger for circular ( 2 + 1 / p ) -flows. In this paper, it is extended for circular λ-flows for all rational numbers λ. This theorem is one of the key tools in the second part of the paper. It was proved by Lovasz et al. (2013) [8] that every ( 6 p + 1 ) -odd-edge-connected graph admits a circular ( 2 + 1 / p ) -flow. In the second part, this result is further extended to other odd integers 6 p + 3 and 6 p − 1 for any positive integer p. We show that (i) every ( 6 p − 1 ) -odd-edge-connected graph admits a circular ( 2 + 2 2 p − 1 ) -flow, and (ii) every ( 6 p + 3 ) -odd-edge-connected graph has flow index strictly less than 2 + 1 / p . Both (i) and (ii) generalize some early results. For example, the case p = 1 of (i) is the well known 4-flow theorem of Jaeger (1979) [4] , and the case p = 1 of (ii) is a recent result by Thomassen and the authors (2018) [7] . The proofs of (i) and (ii) provide (principally different) new approach to those previous results.

A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3. The star chromatic index $$\chi _{st}^\prime $$ (G) of a graph G is the smallest integer k such that G has a star k-edge-coloring. The list star chromatic index $$ch_{st}^\prime $$ (G) is defined analogously. The star edge coloring problem is known to be NP-complete, and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear. In this paper, we study, in contrast, the best linear upper bound for sparse graph classes. We show that for every e > 0 there exists a constant c(e) such that if mad(G) < $${8 \over 3} - \varepsilon $$, then $$ch_{st}^\prime $$ (G) ≤ $${{3{\rm{\Delta }}} \over 2} + c\left( \varepsilon \right)$$ and the coefficient $${3 \over 2}$$ of Δ is the best possible. The proof applies a newly developed coloring extension method by assigning color sets with different sizes.

A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegova et al. independently show that the star chromatic index of a tree with maximum degree Δ is at most ⌊ 3 Δ 2 ⌋ , which is tight. In this paper, we study the list star edge coloring of k -degenerate graphs. Let c h s t ′ ( G ) be the list star chromatic index of G : the minimum s such that for every s -list assignment L for the edges, G has a star edge coloring from L . By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. c h s t ′ ( T ) ≤ ⌊ 3 Δ 2 ⌋ for any tree T with maximum degree Δ . And then by applying some orientation technique we present two upper bounds for list star chromatic index of k -degenerate graphs.

Let τ ( G ) be the maximum number of mutually edge-disjoint spanning trees contained in a graph G and let κ ′ ( G ) denote the edge-connectivity of G . As a corollary of the spanning trees packing theorem by Nash-Williams and Tutte, it is known that if κ ′ ( G ) ≥ 2 k , then τ ( G ) ≥ k . An edge-cut X of G is an essential edge-cut if G − X contains at least two nontrivial components; and G is essentially k -edge-connected if G does not have an essential edge-cut of size less than k . In this paper, we prove that every g -edge-connected, essentially h -edge-connected graph G with g ≥ k + 1 and h ≥ g 2 g − k − 2 satisfies τ ( G ) ≥ k . This result is sharp in the sense that there exist infinitely many graphs showing that neither inequality in the hypothesis can be relaxed. Applications to circular flows of graphs, spanning connectivity of line graphs and supereulerian width of graphs are discussed. In particular, we obtained the following, for given integers g and k with k > 1 and 2 k − 1 ≥ g ≥ k + 1 . (i) Every 5-edge-connected essentially 23-edge-connected graph admits a nowhere-zero 3-flow. (ii) Every 7-edge-connected essentially 47-edge-connected graph has circular flow number less than 3. (iii) Every 8-edge-connected essentially 20-edge-connected planar graph has circular 5 ∕ 2 -flow. (iv) Every g -edge-connected essentially ( ⌈ g 2 g − k ⌉ − 2 )-edge-connected graph has supereulerian width at least k + 1 . (v) For a line graph G = L ( H ) , if G is ( ⌈ g 2 g − k ⌉ − 2 )-connected and δ ( H ) ≥ g , then G is spanning k -connected.

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.

We study the following Steinberg-type problem on circular coloring: for an odd integer $k\ge 3$, what is the smallest number $f(k)$ such that every planar graph of girth $k$ without cycles of length from $k+1$ to $f(k)$ admits a homomorphism to the odd cycle $C_k$ (or equivalently, is circular $(k,\frac{k-1}{2})$-colorable). Known results and counterexamples on Steinberg's Conjecture indicate that $f(3)\in\{6,7\}$. In this paper, we show that $f(k)$ exists if and only if $k$ is an odd prime. Moreover, we prove that for any prime $p\ge 5$, $$p^2-\frac{5}{2}p+\frac{3}{2}\le f(p)\le 2p^2+2p-5.$$ We conjecture that $f(p)\le p^2-2p$, and observe that the truth of this conjecture implies Jaeger's conjecture that every planar graph of girth $2p-2$ has a homomorphism to $C_p$ for any prime $p\ge 5$. Supporting this conjecture, we prove a related fractional coloring result that every planar graph of girth $k$ without cycles of length from $k+1$ to $\lfloor\frac{22k}{3}\rfloor$ is fractional $(k:\frac{k-1}{2})$-colorable for any odd integer $k\ge 5$., Comment: 26 pages, 3 figures, comments welcome

This paper studies a robust optimal investment problem under the mean-variance criterion for a defined contribution (DC) pension plan with an ambiguity-averse member (AAM), who worries about model misspecification and aims to find robust optimal strategy. The member has access to a risk-free asset (i.e., cash or bank account) and a risky asset (i.e., the stock) in a financial market. In order to get closer to the actual environment, we assume that both the income level and stock price are driven by Heston's stochastic volatility model. A continuous-time mean-variance model with ambiguity aversion for a DC pension plan is established. By using the Lagrangian multiplier method and stochastic optimal control theory, the closed-form expressions for robust efficient strategy and efficient frontier are derived. In addition, some special cases are derived in detail. Finally, a numerical example is presented to illustrate the effects of model parameters on the robust efficient strategy and the efficient frontier, and some economic implications have been revealed.

Jaeger, Linial, Payan and Tarsi (JCTB, 1992) introduced the concept of group connectivity as a generalization of nowhere-zero flow for graphs. In this paper, we introduce group connectivity for signed graphs and establish some fundamental properties. For a finite abelian group A , it is proved that an A -connected signed graph is a contractible configuration for A -flow problem of signed graphs. In addition, we give sufficient edge connectivity conditions for signed graphs to be A -connected and study the group connectivity of some families of signed graphs.

A mod ( 2 p + 1 ) -orientation D is an orientation of G such that d D + ( v ) ≡ d D − ( v ) ( mod 2 p + 1 ) for any vertex v ∈ V ( G ) . Extending Tutte’s integer flow conjectures, it was conjectured by Jaeger that every 4 p -edge-connected graph has a mod ( 2 p + 1 ) -orientation. However, this conjecture has been disproved in Han et al. (2018) recently. Infinite families of 4 p -edge-connected graphs (for p ≥ 3 ) and ( 4 p + 1 ) -edge-connected graphs (for p ≥ 5 ) with no mod ( 2 p + 1 ) -orientation are constructed in Han et al. (2018). In this paper, we show that every family of graphs with bounded independence number has only finitely many contraction obstacles for admitting mod ( 2 p + 1 ) -orientations, contrasting to those infinite families. More precisely, we prove that for any integer t ≥ 2 , there exists a finite family F = F ( p , t ) of graphs that do not have a mod ( 2 p + 1 ) -orientation, such that every graph G with independence number at most t either admits a mod ( 2 p + 1 ) -orientation or is contractible to a member in F . This indicates that the problem of determining whether every k -edge-connected graph with independence number at most t admits a mod ( 2 p + 1 ) -orientation is computationally solvable for fixed k and t . In particular, the graph family F ( p , 2 ) is determined, and our results imply that every 8-edge-connected graph G with independence number at most two admits a mod 5-orientation.

It was conjectured by Jaeger that every 4 p-edge-connected graph admits a modulo ( 2 p + 1 ) -orientation (and, therefore, admits a nowhere-zero circular ( 2 + 1 p ) -flow). This conjecture was partially proved by Lovasz et al. (2013) [7] for 6p -edge-connected graphs. In this paper, infinite families of counterexamples to Jaeger's conjecture are presented. For p ≥ 3 , there are 4p-edge-connected graphs not admitting modulo ( 2 p + 1 ) -orientation; for p ≥ 5 , there are ( 4 p + 1 ) -edge-connected graphs not admitting modulo ( 2 p + 1 ) -orientation.

A long-standing conjecture asserts that there exists a constant $c>0$ such that every graph of order $n$ without isolated vertices contains an induced subgraph of order at least $cn$ with all degrees odd. Scott (1992) proved that every graph $G$ has an induced subgraph of order at least $|V(G)|/(2\chi(G))$ with all degrees odd, where $\chi(G)$ is the chromatic number of $G$, this implies the conjecture for graphs with { bounded} chromatic number. But the factor $1/(2\chi(G))$ seems to be not best possible, for example, Radcliffe and Scott (1995) proved $c=\frac 23$ for trees, Berman, Wang and Wargo (1997) showed that $c=\frac 25$ for graphs with maximum degree $3$, so it is interesting to determine the exact value of $c$ for special family of graphs. In this paper, we further confirm the conjecture for graphs with treewidth at most 2 with $c=\frac{2}{5}$, and the bound is best possible., Comment: 13 pages

A mod $(2p+1)$-orientation $D$ is an orientation of $G$ such that $d_D^+(v)-d_D^-(v)\equiv 0 \pmod {2p+1}$ for any vertex $v \in V(G)$. Jaeger conjectured that every $4p$-edge-connected graph has a mod $(2p+1)$-orientation. A graph $G$ is strongly ${\mathbb Z}_{2p+1}$-connected if for every mapping $b: V(G) \mapsto {\mathbb Z}_{2p+1}$ with $\sum_{v\in V(G)}b(v)=0$, there exists an orientation $D$ of $G$ such that $d_D^+(v)-d_D^-(v)= b(v)$ in ${\mathbb Z}_{2p+1}$ for any $v \in V(G)$. A strongly ${\mathbb Z}_{2p+1}$-connected graph admits a mod $(2p+1)$-orientation, and it is a contractible configuration for mod $(2p+1)$-orientation. We prove Jaeger's module orientation conjecture is equivalent to its restriction to bipartite simple graphs and investigate strongly ${\mathbb Z}_{2p+1}$-connectedness of certain bipartite graphs, particularly for $p=2$. We also show that if $G$ is a simple graph with $|V(G)|\ge N(p)= 1152p^4$ and $\min\{\delta(G),\delta(G^c)\}\ge 4p$, then either $G$ or $G^c$ is strongly ${\m...

Tutte’s 3 -flow conjecture states that every 4 -edge-connected graph admits a nowhere-zero 3 -flow. In this paper, we characterize all graphs with independence number at most 4 that admit a nowhere-zero 3 -flow. The characterization of 3 -flow verifies Tutte’s 3 -flow conjecture for graphs with independence number at most 4 and with order at least 21 . In addition, we prove that every odd- 5 -edge-connected graph with independence number at most 3 admits a nowhere-zero 3 -flow. To obtain these results, we introduce a new reduction method to handle odd wheels.

Let k be a positive integer. An adjacent vertex distinguishing (for short, AVD) total k -coloring ϕ of a graph G is a proper total k -coloring of G such that no pair of adjacent vertices have the same set of colors, where the set of colors at a vertex v is { ϕ ( v ) } ∪ { ϕ ( e ) : e is incident to v } . Zhang et al. conjectured in 2005 that every graph with maximum degree Δ has an AVD total ( Δ + 3 ) -coloring. Recently, Papaioannou and Raftopoulou confirmed the conjecture for 4 -regular graphs. In this paper, by applying the Combinatorial Nullstellensatz, we verify the conjecture for all graphs with maximum degree 4.

In this paper we study the flow-property of graphs containing a spanning triangle-tree. Our main results provide a structure characterization of graphs with a spanning triangle-tree admitting a nowhere-zero $3$-flow. All these graphs without nowhere-zero $3$-flows are constructed from $K_4$ by a so-called bull-growing operation. This generalizes a result of Fan et al. in 2008 on triangularly-connected graphs and particularly shows that every $4$-edge-connected graph with a spanning triangle-tree has a nowhere-zero $3$-flow. A well-known classical theorem of Jaeger in 1979 shows that every graph with two edge-disjoint spanning trees admits a nowhere-zero $4$-flow. We prove that every graph with two edge-disjoint spanning triangle-trees has a flow strictly less than $3$., 16 pages, 8 figures

The anti-Ramsey problem was introduced by Erd\H{o}s, Simonovits and S\'{o}s in 1970s. The anti-Ramsey number of a hypergraph $\mathcal{H}$, $ar(n,s, \mathcal{H})$, is the smallest integer $c$ such that in any coloring of the edges of the $s$-uniform complete hypergraph on $n$ vertices with exactly $c$ colors, there is a copy of $\mathcal{H}$ whose edges have distinct colors. In this paper, we determine the anti-Ramsey numbers of linear paths and loose paths in hypergraphs for sufficiently large $n$, and give bounds for the anti-Ramsey numbers of Berge paths. Similar exact anti-Ramsey numbers are obtained for linear/loose cycles, and bounds are obtained for Berge cycles. Our main tools are path extension technique and stability results on hypergraph Tur\'{a}n problems of paths and cycles.

X. Hou, H.-J. Lai, P. Li and C.-Q. Zhang [J. Graph Theory 69 (2012) 464-470] showed that for a simple graph $G$ with $|V(G)|\ge 44$, if $\min\{\delta(G),\delta(G^c)\}\ge 4$, then either $G$ or its complementary graph $G^c$ has a nowhere-zero $3$-flow. In this paper, we improve this result by showing that if $|V(G)|\ge 32$ and $\min\{\delta(G),\delta(G^c)\}\ge 4$, then either $G$ or $G^c$ has flow index strictly less than $3$. Our result is proved by a newly developed closure operation and contraction method., Comment: 16 pages, 4 figures

For a graph G , the flow index ϕ ( G ) is the smallest rational number t > 0 such that the graph has a circular t -flow. Li et al. (2018) recently proved that ϕ ( G ) 3 for any 8-edge-connected graph G , and conjectured that 6-edge-connectivity would suffice. Here we present a contraction method to investigate this problem and apply it to verify this conjecture for certain 6-edge-connected graph families, including chordal graphs, graphs with few odd vertices, and graphs with small independence number.

We study the flow extension of graphs, i.e., pre-assigning a partial flow on the edges incident to a given vertex and aiming to extend to the entire graph. This is closely related to Tutte's $3$-flow conjecture(1972) that every $4$-edge-connected graph admits a nowhere-zero $3$-flow and a $\mathbb{Z}_3$-group connectivity conjecture(3GCC) of Jaeger, Linial, Payan, and Tarsi(1992) that every $5$-edge-connected graph $G$ is $\mathbb{Z}_3$-connected. Our main results show that these conjectures are equivalent to their natural flow extension versions and present some applications. The $3$-flow case gives an alternative proof of Kochol's result(2001) that Tutte's $3$-flow conjecture is equivalent to its restriction on $5$-edge-connected graphs and is implied by the 3GCC. It also shows a new fact that Gr{\"o}tzsch's theorem (that triangle-free planar graphs are $3$-colorable) is equivalent to its seemly weaker girth five case that planar graphs of grith $5$ are $3$-colorable. Our methods allow to verify 3GCC for graphs with crossing number one, which is in fact reduced to the planar case proved by Richter, Thomassen and Younger(2017). Other equivalent versions of 3GCC and related partial results are obtained as well., Comment: 12 pages,3 figures. to appear in European Journal of Combinatorics

Esperet, de Joannis de Verclos, Le and Thomasse in [SIAM J. Discrete Math., 32(1) (2018), 534–542] introduced the problem that for an odd prime p , whether there exists an orientation D of a graph G for any mapping f : E ( G ) → Z p ∗ and any Z p -boundary b of G , such that under D , at every vertex, the net out f -flow is the same as b ( v ) in Z p . Such an orientation D is called an ( f , b ; p ) -orientation of G . Esperet et al. indicated that this problem is closely related to mod p -orientations of graphs, including Tutte’s nowhere zero 3-flow conjecture. Utilizing properties of additive bases and contractible configurations, we show that every graph G with Euler genus g and edge-connectivity κ ′ ( G ) admits an ( f , b ; p ) -orientation for any mapping f : E ( G ) → Z p ∗ and any Z p -boundary b of G , provided κ ′ ( G ) ≥ 4 p − 6 + ⌊ g ∕ 2 ⌋ if g ≤ 2 , ( p − 2 ) ⌊ 6 g + 0 . 25 + 2 . 5 ⌋ + 1 if g ≥ 3 , p 4 . 98 g if g is sufficiently large.

We prove that, for any natural number p , the flow index ϕ ( G ) 2 + 1 p if and only if G has a strongly connected modulo ( 2 p + 1 ) -orientation. For the case p = 1 we prove that the flow index of every 8-edge-connected graph is strictly less than 3.

A parity subgraph of a graph is a spanning subgraph such that the degrees of all vertices have the same parity in both the subgraph and the original graph. Let $$G$$G be a cyclically 6-edge-connected cubic graph. Steffen (Intersecting 1-factors and nowhere-zero 5-flows 1306.5645, 2013) proved that $$G$$G has a nowhere-zero 5-flow if $$G$$G has two perfect matchings with at most two intersections. In this paper, we show that $$G$$G has a nowhere-zero 5-flow if $$G$$G has two parity subgraphs with at most two common edges, which generalizes Steffen's result.