Article
Mathematics, Applied
Yuehua Bu, Qi Jia, Hongguo Zhu, Junlei Zhu
Summary: In this paper, we investigate the acyclic chromatic index of planar graphs without 3-cycles and intersecting 4-cycles. We prove that the acyclic chromatic index is less than or equal to the maximum degree plus 1 when the maximum degree is greater than or equal to 8.
Article
Computer Science, Interdisciplinary Applications
Yuehua Bu, Zewei Zhang, Hongguo Zhu
Summary: In this paper, it is proved that for a planar graph G without adjacent 5-cycles and g(G) = 5 and ?(G) = 17, the 2-distance chromatic number is ? + 3.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2023)
Article
Mathematics
Gyorgy Kiss, Stefko Miklavic, Tamas Szonyi
Summary: This paper discusses the characteristics of finite, connected, simple graphs and the properties of girth-regular graphs. By proving the relationship of characteristic values under certain conditions, a specific range of characteristic values of girth-regular graphs is obtained. In addition, examples of girth-regular graphs are presented.
JOURNAL OF GRAPH THEORY
(2022)
Article
Computer Science, Interdisciplinary Applications
Wei Wei, Qiuyuan Hu, Weidong Yang
Summary: This article proposes a new approximation algorithm for the minimum cut (min-cut) problem in undirected graphs, which can accelerate existing methods by up to 6 orders of magnitude with limited preprocessing overhead. By checking and recording the cut values of various traversal trees, the algorithm estimates the upper bound of the min-cut value between any pair of nodes. Experimental results show that even the serial implementation of the algorithm achieves a larger acceleration ratio compared to existing methods.
ADVANCES IN ENGINEERING SOFTWARE
(2022)
Article
Mathematics, Interdisciplinary Applications
Wei Wei, Haoyi Li, Qinghui Zhang
Summary: The minimum cut problem and its corresponding algorithms have been extensively studied. A recently proposed acceleration strategy based on tree-cut mapping has shown to be effective but with room for improvement. In this study, we propose using bidirectional pruned tree for tree-cut mapping to efficiently find the min-cut of any node pair in dense and sparse graphs.
CHAOS SOLITONS & FRACTALS
(2023)
Article
Mathematics, Applied
Yuehua Bu, Qiang Yang, Junlei Zhu, Hongguo Zhu
Summary: This paper proves that for a planar graph G with g(G) >= 5, Delta(G) >= 20, and without adjacent 5-cycles, the injective chromatic number chi i(G) is less than or equal to Delta(G) + 2.
Article
Mathematics
Min Chen, Andre Raspaud, Weifan Wang, Weiqiang Yu
Summary: This paper proves that every graph in G(5) can be partitioned into (F-3, F-5).
DISCRETE MATHEMATICS
(2023)
Article
Mathematics, Applied
Danjun Huang, Xianxi Wu
Summary: This paper investigates the equitable coloring problem of IC-planar graphs. By proving the theorem, we conclude that every IC-planar graph with a sufficiently large girth can be equitably colored.
Article
Mathematics
Mengjiao Rao, Jianfeng Hou, Qinghou Zeng
Summary: This paper explores a long-standing conjecture in graph theory, confirming optimal bounds for certain cases and establishing partial tight bounds of c for different types of graphs.
GRAPHS AND COMBINATORICS
(2022)
Article
Mathematics, Applied
Frantisek Kardos
Summary: This article translates and summarizes the conjecture and proof of the Hamiltonian property in 3-connected planar cubic graphs.
Article
Mathematics, Applied
Huiqiu Lin, Hangtian Guo
Summary: This paper demonstrates extremal cases under certain conditions and resolves a previously proposed question.
LINEAR ALGEBRA AND ITS APPLICATIONS
(2021)
Article
Computer Science, Information Systems
Wei Wei, Yuting Liu, Qinghui Zhang
Summary: In this paper, an optimal pruned tree-based min-cut acceleration algorithm (PTMA) is proposed for the problem by exploiting the mapping between the cuts and pruned depth-first traversal trees. The algorithm can quickly obtain accurate min-cuts in dense graphs.
INFORMATION SCIENCES
(2024)
Article
Mathematics, Applied
Therese Biedl
Summary: The article proves that any 1-planar graph with a minimum degree of 7 must contain at least 24 vertices, and this is the tightest lower bound.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Mathematics
Kittikorn Nakprasit, Watcharintorn Ruksasakchai, Pongpat Sittitrai
Summary: In this paper, the authors extend previous studies on dynamic programming coloring and list coloring by considering different types of cycles and their adjacency relations. They present a theorem for every planar graph and provide a generalization of previous results.
Article
Mathematics, Applied
Ming Xu, Xiaoyan Cheng, Yuansheng Tang
Summary: This study investigates the properties of bipartite graphs based on specific polynomial structures and discusses and proves the isomorphism in specific cases, demonstrating the validity of the corresponding conclusions.
DISCRETE APPLIED MATHEMATICS
(2021)
