Bilinear and trilinear partitions of a graph (Q1338161)

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.