Bilinear and trilinear partitions of a graph
type: Item
instance of: scholarly article
title: Bilinear and trilinear partitions of a graph
zbMATH Open document ID: 0810.05022
author: E. Sampathkumar
author: L. Pushpalatha
published in: Indian Journal of Pure \& Applied Mathematics
publication date: 1994-12-18T00:00:00Z
review text: The bilinear (resp. trilinear) partition number of a graph \(G\), denoted by \(\chi_{2L}(G)\) (\(\chi_{3L}(G)\), resp.) is defined as the minimum order of a partition \(P\) of \(V(G)\) such that for any two sets \(V_ i\) and \(V_ j\) in \(P\) (three sets \(V_ i\), \(V_ j\) and \(V_ k\) in \(P\), resp.), the subgraph induced by \(V_ i\cup V_ j\) (by \(V_ i\cup V_ j\cup V_ k\), resp.) is a linear forest. Note that \(\chi_{3L}(G)\) exists if and only if \(G\) has no triangle. The authors prove that if \(\Delta\geq 3\) is the maximum degree of \(G\), then \(\chi_{2L}(G)\geq 1+ \lceil\Delta/2\rceil\) and equality holds for trees; \(\chi_{2L}(G)\leq 2+ \lceil\Delta/2\rceil\) if \(G\) is a cactus; \(\chi_{2L}(G)= \max\{\omega(G),1+ \lceil\Delta/2\rceil\}\) if every block of \(G\) is complete, where \(\omega(G)\) is the cliquomatic number of \(G\); \(\chi_{3L}(G)\geq 1+\Delta\) if \(G\) is \(K_ 3\)-free and equality holds for trees; \(\chi_{3L}(G)\leq 2+\Delta\) if \(G\) is a cactus. Some inequalities involving these two numbers, the vertex linear arboricity and the chromatic number of \(G\) are also deduced.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 695831
zbMATH Keywords: partition number
zbMATH Keywords: linear forest
zbMATH Keywords: cliquomatic number
zbMATH Keywords: trees
zbMATH Keywords: cactus
zbMATH Keywords: inequalities
zbMATH Keywords: vertex linear arboricity
zbMATH Keywords: chromatic number
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
Recommended article: Bipartization of graphs
Recommended article: On the bipartition of graphs
Recommended article: Partitions of Graphs
Recommended article: Q4863503
Recommended article: Q3335827
Recommended article: Q3650134
Recommended article: Q5705841
Recommended article: Q4304346
Recommended article: Q3222889
Recommended article: On graphical partitions
description: scientific article; zbMATH DE number 695831