Extremal clique coverings of complementary graphs
type: Item
instance of: scholarly article
title: Extremal clique coverings of complementary graphs
zbMATH Open document ID: 0616.05042
DOI: 10.1007/BF02579256
author: N. J. Pullmann
author: Nicholas Wormald
author: D. de Caen
author: P. Erdős
published in: Combinatorica
publication date: 1986-01-01T00:00:00Z
review text: The clique covering number, \(cc(G)\), is the least number of complete subgraphs needed to cover the edges of \(G\); the clique partition number, \(cp(G)\), is the least number of complete subgraphs needed to partition the edge set of \(G\). Let \(\bar G\) be the complement of \(G\). The paper investigates bounds on \(\max \{cc(G)+cc(\bar G)\}\), \(\max\{cc(G)cc(\bar G)\}\), \(\max\{cp(G)+cp(\bar G)\}\) and \(\max\{cp(G)cp(\bar G)\}\), taken over graphs \(G\) with \(n\) vertices.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 3997836
zbMATH Keywords: extremal problem
zbMATH Keywords: complementary graphs
zbMATH Keywords: clique covering number
zbMATH Keywords: clique partition number
Wikidata QID: Q56850772
MaRDI profile type: Publication
cites work: Q3097395
cites work: The Representation of a Graph by Set Intersections
cites work: Q3922720
cites work: Clique coverings of graphs V: maximal-clique partitions
cites work: Q3313890
full work available at URL: https://doi.org/10.1007/bf02579256
OpenAlex ID: W2138479178
description: scientific article; zbMATH DE number 3997836