Covering graphs by the minimum number of equivalence relations

DOI10.1007/BF02579381zbMath0646.05053WikidataQ100329040 ScholiaQ100329040MaRDI QIDQ1103644

Noga Alon

Publication date: 1986

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

probabilistic argumentsequivalence graphminimum number of complete subgraphsminimum number of equivalence subgraphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Generalized Ramsey theory (05C55)

Related Items (25)

New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings ⋮ Secret-sharing schemes for very dense graphs ⋮ An overview of graph covering and partitioning ⋮ Local Clique Covering of Claw-Free Graphs ⋮ The equivalence number of a line graph ⋮ Avoiding exponential explosion in Petri net models of control flows ⋮ Graphs of small dimensions ⋮ Covering line graphs with equivalence relations ⋮ Set labelling vertices to ensure adjacency coincides with disjointness ⋮ Product dimension of forests and bounded treewidth graphs ⋮ Edge-intersection graphs of boundary-generated paths in a grid ⋮ Edge clique covering sum of graphs ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Unnamed Item ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ A note on induced cycles in Kneser graphs ⋮ Biclique cover and local clique cover of graphs ⋮ Erdős-Pyber theorem for hypergraphs and secret sharing ⋮ On the equivalence covering number of splitgraphs ⋮ On the product dimension of clique factors ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ On set intersection representations of graphs ⋮ On covering graphs by complete bipartite subgraphs ⋮ Secret Sharing Schemes for Dense Forbidden Graphs ⋮ A simple lower bound on edge coverings by cliques

Cites Work

• An extremal problem for sets with applications to graph theory
• On a clique covering problem of Orlin
• Solution of a problem of A. Ehrenfeucht and J. Mycielski
• Covering Graphs by Equivalence Relations
• The Representation of a Graph by Set Intersections
• Unnamed Item
• Unnamed Item

This page was built for publication: Covering graphs by the minimum number of equivalence relations