Graphs with No Induced Five-Vertex Path or Antipath

Maria Chudnovsky; Louis Esperet; Laetitia Lemoine; Peter Maceli; Frédéric Maffray; Irena Penev

doi:10.1002/jgt.22022

Graphs with No Induced Five-Vertex Path or Antipath

Maria Chudnovsky, Louis Esperet, Laetitia Lemoine, Peter Maceli, Frédéric Maffray, Irena Penev

Mathematics

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

3 Scopus citations

Abstract

We prove that a graph G contains no induced five-vertex path and no induced complement of a five-vertex path if and only if G is obtained from 5-cycles and split graphs by repeatedly applying the following operations: substitution, split unification, and split unification in the complement, where split unification is a new class-preserving operation introduced here.

Original language	English (US)
Pages (from-to)	221-232
Number of pages	12
Journal	Journal of Graph Theory
Volume	84
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22022
State	Published - Mar 1 2017

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

P5
decomposition
forbidden subgraph

Access to Document

10.1002/jgt.22022

Cite this

@article{1de7833c1c444f12b5e89d3f0b27fadb,

title = "Graphs with No Induced Five-Vertex Path or Antipath",

abstract = "We prove that a graph G contains no induced five-vertex path and no induced complement of a five-vertex path if and only if G is obtained from 5-cycles and split graphs by repeatedly applying the following operations: substitution, split unification, and split unification in the complement, where split unification is a new class-preserving operation introduced here.",

keywords = "P5, decomposition, forbidden subgraph",

author = "Maria Chudnovsky and Louis Esperet and Laetitia Lemoine and Peter Maceli and Fr{\'e}d{\'e}ric Maffray and Irena Penev",

note = "Publisher Copyright: {\textcopyright} 2016 Wiley Periodicals, Inc.",

year = "2017",

month = mar,

day = "1",

doi = "10.1002/jgt.22022",

language = "English (US)",

volume = "84",

pages = "221--232",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Graphs with No Induced Five-Vertex Path or Antipath

AU - Chudnovsky, Maria

AU - Esperet, Louis

AU - Lemoine, Laetitia

AU - Maceli, Peter

AU - Maffray, Frédéric

AU - Penev, Irena

PY - 2017/3/1

Y1 - 2017/3/1

N2 - We prove that a graph G contains no induced five-vertex path and no induced complement of a five-vertex path if and only if G is obtained from 5-cycles and split graphs by repeatedly applying the following operations: substitution, split unification, and split unification in the complement, where split unification is a new class-preserving operation introduced here.

AB - We prove that a graph G contains no induced five-vertex path and no induced complement of a five-vertex path if and only if G is obtained from 5-cycles and split graphs by repeatedly applying the following operations: substitution, split unification, and split unification in the complement, where split unification is a new class-preserving operation introduced here.

KW - P5

KW - decomposition

KW - forbidden subgraph

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

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

U2 - 10.1002/jgt.22022

DO - 10.1002/jgt.22022

M3 - Article

AN - SCOPUS:84975706605

SN - 0364-9024

VL - 84

SP - 221

EP - 232

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Graphs with No Induced Five-Vertex Path or Antipath

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this