The Representation of a Graph by Set Intersections
From MaRDI portal
Publication:5512009
DOI10.4153/CJM-1966-014-3zbMath0137.43202OpenAlexW2321467776WikidataQ55952638 ScholiaQ55952638MaRDI QIDQ5512009
L. Posa, A. W. Goodman, Paul Erdős
Publication date: 1966
Published in: Canadian Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4153/cjm-1966-014-3
Related Items
Regarding two conjectures on clique and biclique partitions ⋮ Spectral radius and clique partitions of graphs ⋮ Networks beyond pairwise interactions: structure and dynamics ⋮ A compilation of relations between graph invariants ⋮ New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings ⋮ Overlap number of graphs ⋮ Maximum set of edges no two covered by a clique ⋮ Clique coverings of the edges of a random graph ⋮ Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs ⋮ Greedy maximum-clique decompositions ⋮ The \(p\)-intersection number of a complete bipartite graph and orthogonal double coverings of a clique ⋮ Unnamed Item ⋮ Unsupervised feature selection for efficient exploration of high dimensional data ⋮ An overview of graph covering and partitioning ⋮ Greedy clique decompositions and the Turán numbers ⋮ Intersection number and capacities of graphs ⋮ Clique covering of graphs ⋮ The intersection number of complete r-partite graphs ⋮ Minimum \(H\)-decompositions of graphs ⋮ Intersection properties of line graphs ⋮ Covering graphs by the minimum number of equivalence relations ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Turán function and \(H\)-decomposition problem for gem graphs ⋮ Monochromatic Clique Decompositions of Graphs ⋮ A clique covering MIP model for the irregular strip packing problem ⋮ Double-threshold permutation graphs ⋮ Avoiding exponential explosion in Petri net models of control flows ⋮ Graphs of small dimensions ⋮ The minimum number of triangles covering the edges of a graph ⋮ On the intractability landscape of digraph intersection representations ⋮ Tree representations of graphs ⋮ Clique partitions and clique coverings ⋮ Dot product representations of graphs ⋮ On the double competition number ⋮ Optimal guard sets and the Helly property ⋮ Turán number and decomposition number of intersecting odd cycles ⋮ Intersection representation of complete unbalanced bipartite graphs ⋮ Set labelling vertices to ensure adjacency coincides with disjointness ⋮ On graphs of bounded semilattices ⋮ Edge-clique covers of the tensor product ⋮ Forbidden induced subgraphs for bounded \(p\)-intersection number ⋮ Minimum \(H\)-decompositions of graphs: edge-critical case ⋮ Boolean rank of upset tournament matrices ⋮ Constructing an indeterminate string from its associated graph ⋮ Edge clique covering sum of graphs ⋮ Graphs which, with their complements, have certain clique covering numbers ⋮ Complexity of representation of graphs by set systems ⋮ Covers of Eulerian graphs ⋮ On a clique covering problem of Orlin ⋮ Three notions of tropical rank for symmetric matrices ⋮ On the combinatorial problems which I would most like to see solved ⋮ Hardness results for covering arrays avoiding forbidden edges and error-locating arrays ⋮ Triangle-free partial graphs and edge covering theorems ⋮ Clique partitions of distance multigraphs ⋮ Friendship decompositions of graphs ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ On the number of edge disjoint cliques in graphs of given size ⋮ A note on induced cycles in Kneser graphs ⋮ \(H\)-decomposition of \(r\)-graphs when \(H\) is an \(r\)-graph with exactly \(k\) independent edges ⋮ Dominating sequences in grid-like and toroidal graphs ⋮ An improved upper bound and algorithm for clique covers ⋮ Pseudo orthogonal Latin squares ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ Unique intersectability of diamond-free graphs ⋮ A bound on the total size of a cut cover ⋮ Dimension-2 poset competition numbers and dimension-2 poset double competition numbers ⋮ Decomposing toroidal graphs into circuits and edges ⋮ Sphericity, cubicity, and edge clique covers of graphs ⋮ Fast constructive and improvement heuristics for edge clique covering ⋮ On the complexity of directed intersection representation of DAGs ⋮ The intersection numbers of a complex ⋮ On the triangle clique cover and \(K_t\) clique cover problems ⋮ A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\) ⋮ Cycle and cocycle coverings of graphs ⋮ Decomposing uniform hypergraphs into uniform hypertrees and single edges ⋮ Privacy-preserving data splitting: a combinatorial approach ⋮ Large-scale clique cover of real-world networks ⋮ A generalization of the Bollobás set pairs inequality ⋮ Eigenvalues and clique partitions of graphs ⋮ Paired threshold graphs ⋮ An improved error term for minimum \(H\)-decompositions of graphs ⋮ The enumeration of spanning tree of weighted graphs ⋮ Path and cycle decompositions of dense graphs ⋮ On set intersection representations of graphs ⋮ Covering a graph by topological complete subgraphs ⋮ On clique coverings of complete multipartite graphs ⋮ Extremal clique coverings of complementary graphs ⋮ Applications of edge coverings by cliques ⋮ Generalized covering designs and clique coverings ⋮ Covering arrays avoiding forbidden edges ⋮ Covers in hypergraphs ⋮ On clique covers and independence numbers of graphs ⋮ Subgraph coverings and edge switchings ⋮ Upper bounds on the edge clique cover number of a graph ⋮ Completely positive matrices over Boolean algebras and their CP-rank ⋮ Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices ⋮ An Erdős-Gallai conjecture ⋮ Decompositions of triangle-free 5-regular graphs into paths of length five ⋮ On antichain intersection numbers, total clique covers and regular graphs ⋮ Decomposing oriented graphs into transitive tournaments ⋮ On the Decomposition of Graphs ⋮ Clique coverings of graphs V: maximal-clique partitions ⋮ Competition graphs and clique dimensions ⋮ General results on tolerance intersection graphs ⋮ Unnamed Item ⋮ Clique Partitions of Chordal Graphs ⋮ The greedy clique decomposition of a graph ⋮ What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph? ⋮ The 2‐intersection number of paths and bounded‐degree trees ⋮ Edge clique covers in graphs with independence number two ⋮ An algorithm for the decomposition of graphs into cliques ⋮ Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ On graphs with equal coprime index and clique number ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Towards the Erdős-Gallai cycle decomposition conjecture ⋮ Simultaneous intersection representation of pairs of graphs ⋮ Decomposition of Graphs into (k,r)‐Fans and Single Edges ⋮ Decomposing Random Graphs into Few Cycles and Edges ⋮ ON THE COMPLEMENT OF THE ZERO-DIVISOR GRAPH OF A PARTIALLY ORDERED SET ⋮ Optimal path and cycle decompositions of dense quasirandom graphs ⋮ Paul Erdős, 1913-1996 ⋮ On complete subgraphs of different orders ⋮ Orthogonal partitions and covering of graphs ⋮ Turán and Ramsey Properties of Subcube Intersection Graphs ⋮ Kneser Ranks of Random Graphs and Minimum Difference Representations ⋮ Interval digraphs: An analogue of interval graphs ⋮ A survey on the Intersection graphs of ideals of rings ⋮ Monochromatic Kr‐Decompositions of Graphs ⋮ The Drew–Johnson–Loewy conjecture for matrices over max–min semirings ⋮ The graphs of semirings ⋮ On the intersection number of a graph ⋮ Extremal problems in graph theory ⋮ Minimum rainbow \(H\)-decompositions of graphs ⋮ Minimum rainbow \(H\)-decompositions of graphs ⋮ Graph theory ⋮ Decomposing Graphs into Edges and Triangles ⋮ On a problem of G. O. H. Katona and T. Tarján ⋮ Sharp bounds for decomposing graphs into edges and triangles ⋮ Efficient Local Representations of Graphs ⋮ Cycle packing ⋮ Decompositions of Graphs into Fans and Single Edges
