Critical 3-cochromatic graphs
type: Item
instance of: scholarly article
title: Critical 3-cochromatic graphs
zbMATH Open document ID: 0836.05027
DOI: 10.1007/BF01793013
author: Yanyan Li
published in: Graphs and Combinatorics
publication date: 1996-03-26T00:00:00Z
review text: A \(k\)-cocolouring of a graph \(G\) is a colouring of the vertices of \(G\) in \(k\) colours such that, for every colour, the subgraph induced by the vertices of that colour is either a complete graph or an edgeless graph. A graph \(G\) is \(k\)-cochromatic if \(k\) is the smallest number such that \(G\) has a \(k\)-cocolouring. If \(G\) is \(k\)-cochromatic and, for every vertex \(x\) of \(G\), the graph \(G - x\) is \((k - 1)\)-cochromatic then \(G\) is a critical \(k\)-cochromatic graph. In this paper it is shown that every critical 3-cochromatic graph is either an odd cycle or the complement of an odd cycle, or one of 42 graphs on 6 vertices.
reviewed by: Marietjie Frick
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 811347
zbMATH Keywords: cocolouring
zbMATH Keywords: cochromatic number
zbMATH Keywords: critical \(k\)-cochromatic graph
zbMATH Keywords: colouring
zbMATH Keywords: 3-cochromatic graph
zbMATH Keywords: odd cycle
Wikidata QID: Q56428496
MaRDI profile type: Publication
cites work: Critically cochromatic graphs
cites work: Q3139768
cites work: Some topics in cochromatic theory
cites work: Q4175304
cites work: Q4722090
full work available at URL: https://doi.org/10.1007/bf01793013
OpenAlex ID: W2053188290
description: scientific article; zbMATH DE number 811347