Premium
Meyniel's conjecture on graphs of bounded degree
Author(s) -
Hosseini Seyyed Aliasghar,
Mohar Bojan,
Gonzalez Hermosillo de la Maza Sebastian
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22662
Subject(s) - mathematics , conjecture , combinatorics , bounded function , degree (music) , clique sum , discrete mathematics , maximal independent set , indifference graph , chordal graph , trapezoid graph , set (abstract data type) , 1 planar graph , graph , computer science , physics , mathematical analysis , acoustics , programming language
The game of Cops and Robbers is a well‐known pursuit‐evasion game played on graphs. It has been proved that cubic graphs can have arbitrarily large cop number c ( G ) , but the known constructions show only that the set { c ( G ) ∣ Gcubic} is unbounded. In this paper, we prove that there are arbitrarily large subcubic graphs G whose cop number is at least n 1 ∕ 2 − o ( 1 )where n = ∣ V ( G ) ∣ . We also show that proving Meyniel's conjecture for graphs of bounded degree implies a weaker version of Meyniel's conjecture for all graphs.