On the girth of random Cayley graphs

A long-standing conjecture asserts that there is a positive constant c such that every n-vertex graph without isolated vertices contains an induced subgraph with all degrees odd on at least cn vertices. Recently, Ferber and Krivelevich confirmed ...${\mathrm{}}^{\mathrm{}}$${\mathrm{}}^{\mathrm{}}$$\mathrm{}$${}^{\mathrm{}}$${}_{\mathrm{}}$$\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}$

A graph @C is symmetric if its automorphism group acts transitively on the arcs of @C, and s-regular if its automorphism group acts regularly on the set of s-arcs of @C. Tutte [W.T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (...

A proper vertex coloring of a plane graph is 2-facial if any two different vertices joined by a facial walk of length 2 are colored differently, and it is 2-distance if every two vertices at distance 2 from each other are colored differently. Note that ...