×

Random lifts of graphs: Independence and chromatic number. (English) Zbl 0993.05071

For a graph \(G\), a random \(n\)-lift of \(G\) has the vertex set \(V(G)\times [n]\) and for each edge \([u,v]\in E(G)\), there is a random matching between \(\{u\}\times [n]\) and \(\{v\}\times [n]\). This paper proposes bounds on the chromatic number and on the independence number of typical random lifts, with \(G\) fixed and \(n\rightarrow \infty \). For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph, via the entropy functions and Lagrange multipliers. For a base graph \(G\) with chromatic number \(\chi \) and fractional chromatic number \(\chi _{f}\), it is shown that the chromatic number of typical lifts is bounded from below by \(C_{1}\sqrt{\chi /\log \chi }\) and also by \(C_{2}\chi _{f}/\log^{2}\chi _{f}\) for some positive constants \(C_{1}, C_{2}\) (trivially, it is bounded by \(\chi \) from above). There are examples of graphs where the chromatic number of the lift equals \(\chi \) almost surely, and others where it is a.s. \(O(\chi /\log \chi)\). Some open problems are stated.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amit, Combinatorica
[2] and Random lifts of graphs: Edge-expansion, to appear. · Zbl 1095.05034
[3] Bollob?s, Combinatorica 8 pp 49– (1988) · Zbl 0666.05033 · doi:10.1007/BF02122551
[4] and Graph coloring problems, Wiley-Interscience, New York, 1994. · doi:10.1002/9781118032497
[5] Kim, Combin Probab Comput 4 pp 97– (1995) · Zbl 0833.05030 · doi:10.1017/S0963548300001528
[6] Topological methods in combinatorics and geometry. Lecture notes available at: http://www.ms.mff.cuni.cz/acad/kam/matousek/kt.ps.gz, 1994.
[7] Example of the graph with cover degeneracy less than chromatic number. Manuscript, Institute of Mathematics, Novosibirsk, 2000.
[8] Sarkaria, J Combinatorial Theory 49 pp 236– (1990) · Zbl 0714.05001 · doi:10.1016/0095-8956(90)90029-Y
[9] Sarkaria, Proc Amer Math Soc 11 pp 559– (1991) · doi:10.1090/S0002-9939-1991-1004423-6
[10] Models of random regular graphs, Surveys in combinatorics, and (Editors),London Mathematical Society Lecture Note Series, 1999, vol. 276, pp. 239-298. · Zbl 0935.05080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.