On set intersection representations of graphs

DOI10.1002/JGT.20367MaRDI QIDQ3633007zbMATH OpenOpenAlexFDO

Authors Stasys Jukna

Publication date 16 June 2009

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.20367

zbMATH Keywords

intersection graphsBoolean functionsRamsey graphsHadamard graphsbicliquesedge clique covering numberdepth-2 circuitssylvester graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Graphs of small dimensions
• Intersection dimension of bipartite graphs
• Set intersection representations for almost all graphs
• Compact representations of the intersection structure of families of finite sets
• The representation of multi-hypergraphs by set intersections

Cites work

• scientific article; zbMATH DE number 2196516 (Why is no real title available?)
• A Bound for the Chromatic Number of a Graph
• A counterexample to the rank-coloring conjecture
• Covering a graph by complete bipartite graphs
• Covering graphs by the minimum number of equivalence relations
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Covering the edges of a random graph by cliques
• Graph complexity and slice functions
• Graphs of small dimensions
• Linear Circuits over $\operatorname{GF}(2)$
• Modular intersection graphs
• On Graph Complexity
• On covering graphs by complete bipartite subgraphs
• On rank vs. communication complexity
• On the Addressing Problem for Loop Switching
• On the ``log rank-conjecture in communication complexity
• Onp-intersection representations
• Set intersection representations for almost all graphs
• Some combinatorial-algebraic problems from complexity theory
• The Representation of a Graph by Set Intersections
• The \(p\)-intersection number of a complete bipartite graph and orthogonal double coverings of a clique
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• The log-rank conjecture and low degree polynomials
• The power of the middle bit of a \(\#\)P function

Cited in

(19)

• Some lower bounds for the \(L\)-intersection number of graphs
• On representations of graphs as two-distance sets
• On the intractability landscape of digraph intersection representations
• Biclique cover and local clique cover of graphs
• scientific article; zbMATH DE number 7219310 (Why is no real title available?)
• Secret sharing schemes for dense forbidden graphs
• On the intersection graphs associeted to posets
• scientific article; zbMATH DE number 5707918 (Why is no real title available?)
• Biclique covers and partitions
• Directed Intersection Representations and the Information Content of Digraphs
• Bounded-depth succinct encodings and the structure they imply on graphs
• Set intersection representations for almost all graphs
• Erdős-Pyber theorem for hypergraphs and secret sharing
• On the biclique cover of the complete graph
• On covering graphs by complete bipartite subgraphs
• The representation of multi-hypergraphs by set intersections
• On the fine-grained complexity of rainbow coloring
• Entropy of operators or why matrix multiplication is hard for depth-two circuits
• Secret-sharing schemes for very dense graphs

This page was built for publication: On set intersection representations of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3633007)