COPS AND ROBBERS ON P5-FREE GRAPHS*

Maria Chudnovsky; Sergey Norin; Paul D. Seymour; Jeremie Turcotte

doi:10.1137/23M1549912

COPS AND ROBBERS ON P₅-FREE GRAPHS*

Maria Chudnovsky, Sergey Norin, Paul D. Seymour, Jeremie Turcotte

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that every connected P5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5-free graph G with independence number at least three contains a three-vertex induced path with vertices a-b-c in order, such that every neighbor of c is also adjacent to one of a,b.

Original language	English (US)
Pages (from-to)	845-856
Number of pages	12
Journal	SIAM Journal on Discrete Mathematics
Volume	38
Issue number	1
DOIs	https://doi.org/10.1137/23M1549912
State	Published - 2024

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

cop number
cops and robbers
forbidden induced subgraph
P5-free graph

Access to Document

10.1137/23M1549912

Cite this

@article{d9b77c37816f46a0ab0899c849c498a5,

title = "COPS AND ROBBERS ON P5-FREE GRAPHS*",

abstract = "We prove that every connected P5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5-free graph G with independence number at least three contains a three-vertex induced path with vertices a-b-c in order, such that every neighbor of c is also adjacent to one of a,b.",

keywords = "cop number, cops and robbers, forbidden induced subgraph, P5-free graph",

author = "Maria Chudnovsky and Sergey Norin and Seymour, {Paul D.} and Jeremie Turcotte",

year = "2024",

doi = "10.1137/23M1549912",

language = "English (US)",

volume = "38",

pages = "845--856",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - COPS AND ROBBERS ON P5-FREE GRAPHS*

AU - Chudnovsky, Maria

AU - Norin, Sergey

AU - Seymour, Paul D.

AU - Turcotte, Jeremie

PY - 2024

Y1 - 2024

N2 - We prove that every connected P5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5-free graph G with independence number at least three contains a three-vertex induced path with vertices a-b-c in order, such that every neighbor of c is also adjacent to one of a,b.

AB - We prove that every connected P5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5-free graph G with independence number at least three contains a three-vertex induced path with vertices a-b-c in order, such that every neighbor of c is also adjacent to one of a,b.

KW - cop number

KW - cops and robbers

KW - forbidden induced subgraph

KW - P5-free graph

UR - http://www.scopus.com/inward/record.url?scp=85191328955&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85191328955&partnerID=8YFLogxK

U2 - 10.1137/23M1549912

DO - 10.1137/23M1549912

M3 - Article

AN - SCOPUS:85191328955

SN - 0895-4801

VL - 38

SP - 845

EP - 856

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -