Minimum number of disjoint linear forests covering a planar graph |
| |
Authors: | Huijuan Wang Lidong Wu Weili Wu Jianliang Wu |
| |
Institution: | 1. School of Mathematics, Shandong University, Jinan, 250100, China 2. Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75080, USA 3. College of Computer Science and Technology, TaiYuan University of Technology, Taiyuan, Shanxi, 030024, China
|
| |
Abstract: | Graph coloring has interesting real-life applications in optimization, computer science and network design, such as file transferring in a computer network, computation of Hessians matrix and so on. In this paper, we consider one important coloring, linear arboricity, which is an improper edge coloring. Moreover, we study linear arboricity on planar graphs with maximum degree \(\varDelta \ge 7\) . We have proved that the linear arboricity of \(G\) is \(\lceil \frac{\varDelta }{2}\rceil \) , if for each vertex \(v\in V(G)\) , there are two integers \(i_v,j_v\in \{3,4,5,6,7,8\}\) such that any two cycles of length \(i_v\) and \(j_v\) , which contain \(v\) , are not adjacent. Clearly, if \(i_v=i, j_v=j\) for each vertex \(v\in V(G)\) , then we can easily get one corollary: for two fixed integers \(i,j\in \{3,4,5,6,7,8\}\) , if there is no adjacent cycles with length \(i\) and \(j\) in \(G\) , then the linear arboricity of \(G\) is \(\lceil \frac{\varDelta }{2}\rceil \) . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|