Covering graphs by the minimum number of equivalence relations
From MaRDI portal
Publication:1103644
DOI10.1007/BF02579381zbMath0646.05053WikidataQ100329040 ScholiaQ100329040MaRDI QIDQ1103644
Publication date: 1986
Published in: Combinatorica (Search for Journal in Brave)
probabilistic arguments; equivalence graph; minimum number of complete subgraphs; minimum number of equivalence subgraphs
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C55: Generalized Ramsey theory
Related Items
Unnamed Item, Secret-sharing schemes for very dense graphs, The equivalence number of a line graph, Product dimension of forests and bounded treewidth graphs, Erdős-Pyber theorem for hypergraphs and secret sharing, Covering line graphs with equivalence relations, On the equivalence covering number of splitgraphs, Bounded-depth succinct encodings and the structure they imply on graphs, A simple lower bound on edge coverings by cliques, On covering graphs by complete bipartite subgraphs, Representations of graphs and networks (coding, layouts and embeddings), A note on induced cycles in Kneser graphs, Edge-intersection graphs of boundary-generated paths in a grid, Edge clique covering sum of graphs, Biclique cover and local clique cover of graphs, Graphs of small dimensions, On the product dimension of clique factors, An overview of graph covering and partitioning, Avoiding exponential explosion in Petri net models of control flows, New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings, Set labelling vertices to ensure adjacency coincides with disjointness, Dimension-free bounds and structural results in communication complexity, Secret Sharing Schemes for Dense Forbidden Graphs, Local Clique Covering of Claw-Free Graphs, On set intersection representations of graphs
Cites Work