×

Regular graphs with no homomorphisms onto cycles. (English) Zbl 1027.05087

Summary: We prove the existence of \(d\)-regular graphs with arbitrarily large girth and no homomorphism onto the cycle \(C_s\), where \((d,s)= (3,9)\) or \((4, 5)\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B., Random Graphs (1985), Academic Press: Academic Press London · Zbl 0567.05042
[2] Janson, S., Random regular graphs: Asymptotic distributions and contiguity, Combinatorics Probab. Comput., 4, 369-405 (1995) · Zbl 0846.05076
[3] J. H. Kim, and, J. Nešetřil, Colorings of graphs with small degrees, manuscript.; J. H. Kim, and, J. Nešetřil, Colorings of graphs with small degrees, manuscript.
[4] A. V. Kostočka, J. Nešetřil, and, P. Smolikova, Complexity of coloring of bounded degree graphs, Discrete Math, to appear.; A. V. Kostočka, J. Nešetřil, and, P. Smolikova, Complexity of coloring of bounded degree graphs, Discrete Math, to appear.
[5] Lai, H.-J., Unique graph homomorphisms onto odd cycles, II, J. Combin. Theory Ser. B, 46, 363-376 (1989) · Zbl 0706.05020
[6] McKay, B. D., Independent sets in regular graphs of high girth, Proc. Australia- Singapore Joint Conference on Information Processing and Combinatorial Mathematics, Singapore, 1986 (1987), p. 179-185 · Zbl 0644.05028
[7] Molloy, M.; Robalewska, H.; Robinson, R. W.; Wormald, N. C., 1-factorisations of random regular graphs, Random Structures Algorithms, 10, 305-321 (1997) · Zbl 0974.05062
[8] Wormald, N. C., Models of random regular graphs, (Lamb, J. D.; Preece, D. A., Surveys in Combinatorics, 1999 (1999), Cambridge University Press: Cambridge University Press Cambridge), 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.