ZLZuosong Liang

Zuosong Liang

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Zuosong Liang has a total of 18 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The 2-Maxian Problem on Block Graphs with Distance Constraint

    by Chunsong Bai, Zuosong Liang

    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

    On the $ 3 $-coloring of planar graphs without cycles of length from $ 4 $ to $ 6 $

    by Zuosong Liang, Danzhang Liao, Chunsong Bai

    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.

  • Planar graphs without 4-, 5-, 7-cycles and special 9-cycles are near-bipartite

    by Feng Lv, Zuosong Liang, Danzhang Liao

    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

    The 3-Coloring of Planar Graphs with Adjacent Triangles

    by Zuosong Liang, Xin Xue

    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.

  • Spanning trees with few branch vertices in K1,4-free graphs

    by Junqing Cai, Huiming Zhai, Zuosong Liang

  • Open Access

    On Hamiltonian Decomposition Problem of 3-Arc Graphs

    by Guangjun Xu, Qiang Sun, Zuosong Liang

    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

    The Connected P‐Median Problem on Cactus Graphs

    by Chunsong Bai, Jianjie Zhou, Zuosong Liang

    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

    A Linear‐Time Algorithm for 4‐Coloring Some Classes of Planar Graphs

    by Zuosong Liang, Huandi Wei

    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.