A graph G is a fractional (a,b,n)-critical graph if removing any n vertices from G, the resulting subgraph still admits a fractional [a,b]-factor. In this paper, we determine the exact tight isolated toughness bound for fractional (a,b,n)-critical graphs. To be specific, a graph G is fractional (a,b,n)-critical if δ(G)≥a+n and I(G)>a−1+n+1na,b, where na,b≥2 is an integer satisfies (na,b−1)a≤b≤na,ba−1. Furthermore, the sharpness of bounds is showcased by counterexamples. Our contribution improves a result from [W. Gao, W. Wang, and Y. Chen, Tight isolated toughness bound for fractional (k,n)-critical graphs, Discrete Appl. Math. 322 (2022), 194–202] which established the tight isolated toughness bound for fractional (k,n)-critical graphs.

Graph fractional factor theory plays a crucial role in data transmission and network flow existence analysis, and has become one of the hot research branches of graph theory. This paper introduces fuzzy fractional factor in fuzzy graph setting, and an algorithm-based proof of its necessary and sufficient condition is given. The transformation operation is introduced to show that any two fuzzy fractional f $f$ -factors can be converted between each other, and the characteristic of maximum fuzzy fractional factor through increasing walk is determined. Finally, toughness in fuzzy graph setting is introduced, and preliminary toughness bound for fuzzy fractional ι $\iota $ -factor is presented, where ι = min e ∈ E { μ B ( e ) ∣ μ B ( e ) > 0 } $\iota ={\min }_{e\in E}\{{\mu }_{B}(e)| {\mu }_{B}(e)\gt 0\}$ .

The issues of ruggedness and vulnerability are cruxes in network security research, which must be considered during the network designing phase. Parameters such as toughness, isolated toughness, and binding number characterize the vulnerable of the network from the structure of networks. The path factor, a special case of the generalized ℋ -factor, measures the feasibility of data transmission in networks. Recent advances have been obtained to show that there is an inevitable connection between the vulnerability parameters of the network and the existence of path factors, while we found that some existing theoretical results are not tight and there is still a long way for further improvement. In view of graph theory approaches, this paper mainly contributes to determine the sharp bounds of toughness, isolated toughness, and binding number for the existence of path factor in different settings, and therefore solve the open problems left unsolved in previous articles.

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 condition that two pairs of crossing edges have no common end-vertices. It is shown in this paper that every IC-planar graph is 6-choosable.

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

We consider the following firefighter problem on a graph $G=(V,E)$. Initially, a fire breaks out at a vertex v of G. In each subsequent time unit, a firefighter protects one vertex, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. Let $\mathrm{sn}(v)$ denote the maximum number of vertices the firefighter can save when a fire breaks out at vertex v of G. We define the surviving rate $\rho(G)$ of G to be the average percentage of vertices that can be saved when a fire randomly breaks out at a vertex of G, i.e., $\rho(G)=\sum_{v\in V}\mathrm{sn}(v)/n^2$. In this paper, we prove that for every tree T on n vertices, $\rho(T)>1-\sqrt{2/n}$. Furthermore, we show that $\rho(G)>1/6$ for every outerplanar graph G, and $\rho(H)>3/10$ for every Halin graph H with at least 5 vertices.

For a planar graph G, let $\Delta(G)$, $g(G)$, and $\lambda(G;p,q)$ denote, respectively, its maximum degree, girth, and $L(p,q)$-labeling number. We prove that (1) $\lambda(G;p,q)\le (2q-1)\Delta(G)+4p+4q-4$ if $g(G)\ge 7$; (2) $\lambda(G;p,q)\le (2q-1)\Delta(G)+6p+12q-9$ if $g(G)\ge 6$; (3) $\lambda(G;p,q)\le (2q-1)\Delta(G)+6p+24q-15$ if $g(G)\ge 5$. These bounds have consequences on conjectures by Wegner [Graphs with Given Diameter and a Coloring Problem, preprint, University of Dortmund, Dortmund, Germany, 1977] and Griggs and Yeh [SIAM J. Discrete Math., 5 (1992), pp. 586--595].

Let G be a planar graph without two triangles sharing a common vertex. We prove that (1) G is 4-choosable and (2) G is edge-$(\Delta(G)+1)$-choosable when its maximum degree $\Delta(G)\ne 5$.