What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov complexity of a graph? Does it make sense to define something in this line at all? I guess one needs a binary string, first of all. Is there then a way to get a binary string from a graph in some unequivocal way, without having to deal with labeling issues, permutations, etc.?

Li and Vitányi in their standard textbook on Kolmogorov complexity (3rd edition, p.456) observe
This is made more precise in Section 6.4. In particular, they show that the number of distinct isomorphism classes of undirected graphs with $n$ vertices asymptotically approaches $2^\binom{n}{2}/n!$, with only a small error. By Stirling's approximation, the Kolmogorov complexity of undirected graphs with $n$ vertices can then be seen to be close to $n(n1)/2 + c$ bits. For undirected graphs the adjacency matrix is symmetric and has 0's on the diagonal, so one only needs to store the $n(n1)/2$ bits above the diagonal. This makes more precise the claim made in another answer, that the adjacency matrix representation is optimal. (Note that close in this argument may still be an unbounded function of $n$; see also Lemma 6.4.6 and the comment after it.)



this question is closely related to a field called graph complexity in computational complexity theory. there are many compression algorithms possible, any standard one from computer science will suffice. however one fairly natural graph compression algorithm is to represent them via circuits (DAGs). in this way circuits can be used to construct more complex graphs out of simpler "basic" graphs. there are some foremost problems (eg in complexity class separations) expressible in this area/framework. for example NP$\stackrel{?}{\subset}$P/poly is open, is a stronger conjecture than P$\neq$NP (because its the nonuniform version vs uniform case where Kolmogorov complexity is more associated with uniform circuits), and can be expressed as a lower bound associated with building graphs out of stars using monotone circuits (AND/OR operations only on edge sets). see this nice survey, Computational Complexity of Graphs by Stasys Jukna 


it depends on whether the graphs you want to compress have any particular repeated "structure" in the sense of something that can be recognized by an algorithm or if they are random (you dont specify suggest you edit question or specify this in comments for better feedback). if the graphs are random, compression is not possible just as theory predicts that "most strings are random". "random" graphs here can be roughly defined as a graph such that half of all the possible edges are distributed randomly. sparse graphs can be "compressed" in the sense that if you store only the edges that are present thats an improvement over storing a list of all edges with '1' or '0' for edge present or absent). nobody so far has suggested the somewhat obvious strategy for dense graphs of storing the inverse and then compressing that. any possible existing data compression algorithm can be used on graphs by converting the graph into a string using some conversion algorithm (ie 11 mapping between strings and graphs) and various conversion algorithms vs. the graph structure would affect how much the graph can be compressed. the question is also very much related to the question, "what are different ways/data structures to store graphs, esp those that take into acct repeated structures in the graph". 


While searching for a definition of chromatic entropy, I found a link that might prove helpful to you: Entropy, Orbits, and Spectra of Graphs by A. Mowshowitz and V. Mitsou. In particular, they summarize results that study complexity of graphs by characterizing it in terms of entropy, information content of graphs, etc. 


Graph compression algorithms are starting to be used in biological applications (e.g. Itzkovitz, et al. Coarsegraining and selfdissimilarity of complex networks; L. Peshkin, Structure induction by lossless graph compression; M. Hayashida and T. Akutsu Comparing biological networks via graph compression). Unlike the pure mathematical side, the networks involved are not the whole class of (nonisomorphic) (un)labelled graphs. Motivated by string compression, these algorithms can detect frequently occurring induced subgraphs. Recently, the related topic of network motifs (small connected subgraphs that occur as an induced subgraph significantly more frequently than in randomized networks) has received an explosion of interest. It is hoped that graph compression algorithms can provide insight into network motifs (and other small induced sugraphs, or "graphlets"), and thus provide insight into the (biological) network as a whole. 


Each graph can be uniquelly represented as an adjacency matrix. This is simply an nxn matrix of values 0,1. Each graph can therefore be expressed uniquely as a string of length n^2 by sequentially concatenating each line. Graphs with cycles and directed graphs are also uniquely represented. Examples: From this representation and from kolmogorov complexity certain statements become evident. (1) For any other representation of graphs, there exists a constant c such that the conditional kolgomorov complexity on this representation saves at most c bits from the kolmogorov complexity from adjacency matrix. (2) Sparse graphs are highly compressible (adjacency matrix of sparse graph contain a lot of zeroes versus very few ones) (3) if all you care about is about equivalency classes between graphs. 

