pith. sign in

arxiv: 1308.3385 · v1 · pith:OWZKAMAYnew · submitted 2013-08-15 · 🧮 math.CO

Meyniel's conjecture on the cop number: a survey

classification 🧮 math.CO
keywords conjecturemeynielgraphnumberordersqrtsurveyattention
0
0 comments X
read the original abstract

Meyniel's conjecture is one of the deepest open problems on the cop number of a graph. It states that for a connected graph $G$ of order $n,$ $c(G) = O(\sqrt{n}).$ While largely ignored for over 20 years, the conjecture is receiving increasing attention. We survey the origins of and recent developments towards the solution of the conjecture. We present some new results on Meyniel extremal families containing graphs of order $n$ satisfying $c(G) \ge d\sqrt{n},$ where $d$ is a constant.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.