Contents

Ars Combinatoria

  • Research article

Linear Vertex Arboricity, Independence Number and Clique Cover Number

Peter Che Bor Lam 1, Wai Chee Shiu1, Feng Sun2, Jianfang Wang3, Guiying Yan4
1Department of Mathematics Hong Kong Baptist University
2Rally International Inc. Forest Park, I] 60130, USA
3Institute of Applied Mathematics Chinese Academy of Sciences and Asia-Pacific Operational Research Center Beijing, China
4Institute of Applied Mathematics Chinese Academy of Sciences Beijing, China
  • Published: 31/01/2001

Abstract

The linear vertex-arboricity of a graph \(G\) is defined as the minimum number of subsets into which the vertex-set \(V(G)\) can be partitioned so that every subset induces a linear forest. In this paper, we give the upper and lower bounds for the sum and product of linear vertex-arboricity with independence number and with clique cover number, respectively. All of these bounds are sharp.

Citation
Peter Che Bor Lam , Wai Chee Shiu, Feng Sun, Jianfang Wang, Guiying Yan. Linear Vertex Arboricity, Independence Number and Clique Cover Number[J], Ars Combinatoria, Volume 058. 121-128. .