A lower bound on cochromatic number for line graphs of a kind of graphs
type: Item
instance of: scholarly article
title: A lower bound on cochromatic number for line graphs of a kind of graphs
zbMATH Open document ID: 1109.05045
author: Xinsheng Liu
author: Xiang'en Chen
author: Lifeng Ou
published in: Applied Mathematics. Series B (English Edition)
publication date: 2006-12-05T00:00:00Z
review text: A \(t\)-cocoloring of a graph \(G\) is a partition of \(V(G)\) into \(t\) sets such that each set of the partition induces an empty graph or a complete graph. \(G\) is \(t\)-cocolorable if \(G\) has a \(t\)-cocoloring. The cochromatic number of \(G\), denoted \(z(G)\), is \(z(G)=\min\{t:G\) is \(t\)-cocolorable\}. \textit{P. Erdős, J. Gimbel} and \textit{H. J. Straight} [Eur. J. Comb. 11, 235--240 (1990; Zbl 0721.05020)] conjectured that if \(\omega(G)<5\) and \(z(G)>3\) then \(z(G)\geq\chi (G)-2\). It is shown here that if \(G\) is a line graph of a connected graph \(G\) with \(\omega(G)<5\) and \(G\neq K_4\), then \(z(G)\geq\chi(G)-2\), where \(\omega(G)\) is the clique number of \(G\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5077212
zbMATH Keywords: partition
zbMATH Keywords: clique number
reviewed by: Linda Lesniak
MaRDI profile type: Publication
full work available at URL: s11766-003-0013-6
OpenAlex ID: W2325367774
cites work: Q3097395
cites work: Q4175304
cites work: Chromatic number versus chromatic number in graphs with bounded clique number
DOI: 10.1007/S11766-003-0013-6
description: scientific article; zbMATH DE number 5077212