Zuosong Liang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Zuosong Liang has a total of 18 co-authors. Here are the top co-authors by number of shared publications:
Chunsong Bai
School of Mathematics, Guangxi Minzu University, Nanning 530006, China
2 shared publicationsDanzhang Liao
2 shared publications- Chunsong Bai
School of Finance and Mathematics, Huainan Normal University, Huainan, China
1 shared publication - Chunsong Bai
School of Finance and Mathematics, Huainan Normal University, Huainan 232038, China
1 shared publication - Erfang Shan
School of Management, Shanghai University, Shanghai, China
1 shared publication Feng Lv
School of Mathematics, Guangxi Minzu University, Nanning 530006, P. R. China
1 shared publication
Latest Publications
- Open Access
- 30 June 2026
- Published by MDPI AG in Preprints.org
The 2-Maxian Problem on Block Graphs with Distance Constraint
This paper investigates the constrained 2-maxian problem defined on block graphs, a special class of composite graphs containing trees and cacti as subclasses. The problem requires placing two facilities on a block graph such that the Euclidean/topological distance between the two facilities is bounded by a given upper limit, while maximizing the total weighted maximum distance from all client vertices to the nearest facility. We first analyze the structural properties of block graphs and the vertex optimality of the constrained 2-maxian solution, proving that at least one facility in any optimal solution must be located at a vertex of the block graph. Based on this key property, we design an efficient polynomial-time algorithm for the constrained 2-maxian problem on block graphs. We further discuss the differences and connections between constrained and unconstrained 2-maxian problems, and compare the proposed method with existing algorithms for trees, cycles and cactus graphs. Numerical analysis verifies the correctness and efficiency of the algorithm.
- 30 June 2026
- Published by MDPI AG in Preprints.org
Open AccessThe 2-Maxian Problem on Block Graphs with Distance Constraint
This paper investigates the constrained 2-maxian problem defined on block graphs, a special class of composite graphs containing trees and cacti as subclasses. The problem requires placing two facilities on a block graph such that the Euclidean/topological distance between the two facilities is bounded by a given upper limit, while maximizing the total weighted maximum distance from all client vertices to the nearest facility. We first analyze the structural properties of block graphs and the vertex optimality of the constrained 2-maxian solution, proving that at least one facility in any optimal solution must be located at a vertex of the block graph. Based on this key property, we design an efficient polynomial-time algorithm for the constrained 2-maxian problem on block graphs. We further discuss the differences and connections between constrained and unconstrained 2-maxian problems, and compare the proposed method with existing algorithms for trees, cycles and cactus graphs. Numerical analysis verifies the correctness and efficiency of the algorithm.
- Open Access
- 1 January 2026
- Published by American Institute of Mathematical Sciences (AIMS) in AIMS Mathematics
- Vol. 11 (5) , 12895-12909
On the $ 3 $-coloring of planar graphs without cycles of length from $ 4 $ to $ 6 $In $ 1976 $, Steinberg conjectured that every planar graph without $ 4 $- and $ 5 $-cycles is $ 3 $-colorable. This conjecture was proved false by Cohen-Addad et al in 2017. Erdős raised the following question: Is there an integer $ k $ such that every planar graph without cycles of length from $ 4 $ to $ k $ is $ 3 $-colorable? Borodin et al. proved that every planar graph without cycles of length from $ 4 $ to $ 7 $ is $ 3 $-colorable [Planar graphs without cycles of length from $ 4 $ to $ 7 $ are $ 3 $-colorable, J. Combin.Theory Ser. B, 93 (2005), 303–311]. However, the question whether every planar graph without cycles of length from $ 4 $ to $ 6 $ is $ 3 $-colorable is not answered yet and full of challenges. A $ 7 $-cycle is called a special $ 7 $-cycle if it shares an edge with another $ 7 $-cycle or $ 9 $-cycle. In this paper, we prove that every planar graph without cycles of length from $ 4 $ to $ 6 $ and without special $ 7 $-cycles is $ 3 $-colorable which is an improvement of Borodin's result.- 1 January 2026
- Published by American Institute of Mathematical Sciences (AIMS) in AIMS Mathematics
- Vol. 11 (5) , 12895-12909
Open AccessOn the $ 3 $-coloring of planar graphs without cycles of length from $ 4 $ to $ 6 $In $ 1976 $, Steinberg conjectured that every planar graph without $ 4 $- and $ 5 $-cycles is $ 3 $-colorable. This conjecture was proved false by Cohen-Addad et al in 2017. Erdős raised the following question: Is there an integer $ k $ such that every planar graph without cycles of length from $ 4 $ to $ k $ is $ 3 $-colorable? Borodin et al. proved that every planar graph without cycles of length from $ 4 $ to $ 7 $ is $ 3 $-colorable [Planar graphs without cycles of length from $ 4 $ to $ 7 $ are $ 3 $-colorable, J. Combin.Theory Ser. B, 93 (2005), 303–311]. However, the question whether every planar graph without cycles of length from $ 4 $ to $ 6 $ is $ 3 $-colorable is not answered yet and full of challenges. A $ 7 $-cycle is called a special $ 7 $-cycle if it shares an edge with another $ 7 $-cycle or $ 9 $-cycle. In this paper, we prove that every planar graph without cycles of length from $ 4 $ to $ 6 $ and without special $ 7 $-cycles is $ 3 $-colorable which is an improvement of Borodin's result. - 27 October 2025
- Published by World Scientific Pub Co Pte Ltd in Discrete Mathematics, Algorithms and Applications
Planar graphs without 4-, 5-, 7-cycles and special 9-cycles are near-bipartite
A graph is near-bipartite if its vertex set can be partitioned into two parts such that one part is an independent set and the other induces a forest. It is clear that near-bipartite graphs are [ ]-colorable. It was proved by Borodin et al. [Planar graphs without 5- and [ ]-cycles and without adjacent triangles are [ ]-colorable, J. Combin. Theory Ser. B 99 (2009) 668–673] and independently by Xu [On [ ]-colorable plane graphs without [ ]- and [ ]-cycles, J. Combin. Theory Ser. B 96 (2006) 958–963] that planar graphs without [ ]-, [ ]-, [ ]-cycles are [ ]-colorable. Kang, Lu and Jin [(I,F)-partition of planar graphs without cycles of length 4,6,or 9, Discuss. Math. Graph Theory 45 (2025) 129–150] asked that whether it is true that planar graphs without [ ]-, [ ]-, [ ]-cycles are near-bipartite. A [ ]-cycle is called a special [ ]-cycle if this [ ]-cycle shares exactly one edge with a triangle of [ ]. In this paper, we prove that planar graphs without [ ]-, [ ]-, [ ]-cycles and without special [ ]-cycles are near-bipartite.
- 27 October 2025
- Published by World Scientific Pub Co Pte Ltd in Discrete Mathematics, Algorithms and Applications
Planar graphs without 4-, 5-, 7-cycles and special 9-cycles are near-bipartite
A graph is near-bipartite if its vertex set can be partitioned into two parts such that one part is an independent set and the other induces a forest. It is clear that near-bipartite graphs are [ ]-colorable. It was proved by Borodin et al. [Planar graphs without 5- and [ ]-cycles and without adjacent triangles are [ ]-colorable, J. Combin. Theory Ser. B 99 (2009) 668–673] and independently by Xu [On [ ]-colorable plane graphs without [ ]- and [ ]-cycles, J. Combin. Theory Ser. B 96 (2006) 958–963] that planar graphs without [ ]-, [ ]-, [ ]-cycles are [ ]-colorable. Kang, Lu and Jin [(I,F)-partition of planar graphs without cycles of length 4,6,or 9, Discuss. Math. Graph Theory 45 (2025) 129–150] asked that whether it is true that planar graphs without [ ]-, [ ]-, [ ]-cycles are near-bipartite. A [ ]-cycle is called a special [ ]-cycle if this [ ]-cycle shares exactly one edge with a triangle of [ ]. In this paper, we prove that planar graphs without [ ]-, [ ]-, [ ]-cycles and without special [ ]-cycles are near-bipartite.
- Open Access
- 1 September 2025
- Published by Global Science Press in Annals of Applied Mathematics
- Vol. 41 (3) , 302-312
The 3-Coloring of Planar Graphs with Adjacent Triangles
Erdős raised the following problem according to Steinberg’s conjecture: Is there an integer such that every planar graph without cycles of length from 4 to $k$ is 3-colorable. By far, the result about the problem was improved to $k≤7$ by Borodin et al. However, by permitting the existence of adjacent triangles except $K_4$, for an arbitrary integer $k≥5,$ there exists a planar graph without cycles of length from 5 to $k$ such that $G$ is not 3-colorable. Let $d$ denote the minimum distance between two diamonds in $G$, where a diamond is the union of two adjacent triangles. In this paper, we prove that a planar graph $G$ with $d≥2$ and without cycles of length from 5 to 18 is 3-colorable. The reader is invited to find the smallest integer $k$ such that a planar graph $G$ with $d≥2$ and without cycles of length from 5 to $k$ is 3-colorable.- 1 September 2025
- Published by Global Science Press in Annals of Applied Mathematics
- Vol. 41 (3) , 302-312
Open AccessThe 3-Coloring of Planar Graphs with Adjacent Triangles
Erdős raised the following problem according to Steinberg’s conjecture: Is there an integer such that every planar graph without cycles of length from 4 to $k$ is 3-colorable. By far, the result about the problem was improved to $k≤7$ by Borodin et al. However, by permitting the existence of adjacent triangles except $K_4$, for an arbitrary integer $k≥5,$ there exists a planar graph without cycles of length from 5 to $k$ such that $G$ is not 3-colorable. Let $d$ denote the minimum distance between two diamonds in $G$, where a diamond is the union of two adjacent triangles. In this paper, we prove that a planar graph $G$ with $d≥2$ and without cycles of length from 5 to 18 is 3-colorable. The reader is invited to find the smallest integer $k$ such that a planar graph $G$ with $d≥2$ and without cycles of length from 5 to $k$ is 3-colorable. - 16 August 2024
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 40 (5) , 1-9
On the Complexity of Local-Equitable Coloring in Claw-Free Graphs with Small Degree
- 16 August 2024
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 40 (5) , 1-9
On the Complexity of Local-Equitable Coloring in Claw-Free Graphs with Small Degree
- 8 April 2024
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (7)
Spanning trees with few branch vertices in K1,4-free graphs
- 8 April 2024
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (7)
Spanning trees with few branch vertices in K1,4-free graphs
- 19 December 2022
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 39 (1) , 1-5
A Generalization of Grötzsch Theorem on the Local-Equitable Coloring
- 19 December 2022
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 39 (1) , 1-5
A Generalization of Grötzsch Theorem on the Local-Equitable Coloring
- Open Access
- 28 April 2022
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2022, 1-6
On Hamiltonian Decomposition Problem of 3-Arc Graphs
A 4-tuple in a graph is a 3-arc if each of and is a path. The 3-arc graph of is the graph with vertex set all arcs of and edge set containing all edges joining and whenever is a 3-arc of . A Hamilton cycle is a closed path meeting each vertex of a graph. A graph including a Hamilton cycle is called Hamiltonian and has a Hamiltonian decomposition provided its edge set admits a partition into disjoint Hamilton cycles (possibly with a single perfect matching). The current paper proves that every connected 3-arc graph consists of more than one Hamilton cycle. Since the 3-arc graph of a cubic graph is 4-regular, it further proves that each 3-arc graph of a cubic graph in a certain family has a Hamiltonian decomposition.
- 28 April 2022
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2022, 1-6
Open AccessOn Hamiltonian Decomposition Problem of 3-Arc Graphs
A 4-tuple in a graph is a 3-arc if each of and is a path. The 3-arc graph of is the graph with vertex set all arcs of and edge set containing all edges joining and whenever is a 3-arc of . A Hamilton cycle is a closed path meeting each vertex of a graph. A graph including a Hamilton cycle is called Hamiltonian and has a Hamiltonian decomposition provided its edge set admits a partition into disjoint Hamilton cycles (possibly with a single perfect matching). The current paper proves that every connected 3-arc graph consists of more than one Hamilton cycle. Since the 3-arc graph of a cubic graph is 4-regular, it further proves that each 3-arc graph of a cubic graph in a certain family has a Hamiltonian decomposition.
- Open Access
- 1 January 2021
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2021 (1) , 3533623
The Connected P‐Median Problem on Cactus Graphs
This study deals with the facility location problem of locating a set Vp of p facilities on a graph such that the subgraph induced by Vp is connected. We consider the connected p‐median problem on a cactus graph G whose vertices and edges have nonnegative weights. The aim of a connected p‐median problem is to minimize the sum of weighted distances from every vertex of a graph to the nearest vertex in Vp. We provide an O(n2p2) time algorithm for the connected p‐median problem, where n is the number of vertices.
- 1 January 2021
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2021 (1) , 3533623
Open AccessThe Connected P‐Median Problem on Cactus Graphs
This study deals with the facility location problem of locating a set Vp of p facilities on a graph such that the subgraph induced by Vp is connected. We consider the connected p‐median problem on a cactus graph G whose vertices and edges have nonnegative weights. The aim of a connected p‐median problem is to minimize the sum of weighted distances from every vertex of a graph to the nearest vertex in Vp. We provide an O(n2p2) time algorithm for the connected p‐median problem, where n is the number of vertices.
- Open Access
- 1 January 2021
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2021 (1)
A Linear‐Time Algorithm for 4‐Coloring Some Classes of Planar Graphs
Every graph G = (V, E) considered in this paper consists of a finite set V of vertices and a finite set E of edges, together with an incidence function that associates each edge e ∈ E of G with an unordered pair of vertices of G which are called the ends of the edge e. A graph is said to be a planar graph if it can be drawn in the plane so that its edges intersect only at their ends. A proper k‐vertex‐coloring of a graph G = (V, E) is a mapping c : V⟶S (S is a set of k colors) such that no two adjacent vertices are assigned the same colors. The famous Four Color Theorem states that a planar graph has a proper vertex‐coloring with four colors. However, the current known proof for the Four Color Theorem is computer assisted. In addition, the correctness of the proof is still lengthy and complicated. In 2010, a simple O(n2) time algorithm was provided to 4‐color a 3‐colorable planar graph. In this paper, we give an improved linear‐time algorithm to either output a proper 4‐coloring of G or conclude that G is not 3‐colorable when an arbitrary planar graph G is given. Using this algorithm, we can get the proper 4‐colorings of 3‐colorable planar graphs, planar graphs with maximum degree at most five, and claw‐free planar graphs.
- 1 January 2021
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2021 (1)
Open AccessA Linear‐Time Algorithm for 4‐Coloring Some Classes of Planar Graphs
Every graph G = (V, E) considered in this paper consists of a finite set V of vertices and a finite set E of edges, together with an incidence function that associates each edge e ∈ E of G with an unordered pair of vertices of G which are called the ends of the edge e. A graph is said to be a planar graph if it can be drawn in the plane so that its edges intersect only at their ends. A proper k‐vertex‐coloring of a graph G = (V, E) is a mapping c : V⟶S (S is a set of k colors) such that no two adjacent vertices are assigned the same colors. The famous Four Color Theorem states that a planar graph has a proper vertex‐coloring with four colors. However, the current known proof for the Four Color Theorem is computer assisted. In addition, the correctness of the proof is still lengthy and complicated. In 2010, a simple O(n2) time algorithm was provided to 4‐color a 3‐colorable planar graph. In this paper, we give an improved linear‐time algorithm to either output a proper 4‐coloring of G or conclude that G is not 3‐colorable when an arbitrary planar graph G is given. Using this algorithm, we can get the proper 4‐colorings of 3‐colorable planar graphs, planar graphs with maximum degree at most five, and claw‐free planar graphs.