Excluding the fork and antifork

Maria Chudnovsky; Linda Cook; Paul Seymour

doi:10.1016/j.disc.2019.111786

Excluding the fork and antifork

Mathematics

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

5 Scopus citations

Abstract

The fork is the tree obtained from the claw K_1,3 by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs that do not contain the fork or antifork as induced subgraphs.

Original language	English (US)
Article number	111786
Journal	Discrete Mathematics
Volume	343
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2019.111786
State	Published - May 2020

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Antifork
Forbidden induced subgraph
Fork
Graph structure

Access to Document

10.1016/j.disc.2019.111786

Cite this

@article{1585fd5ab64f450faf772898a268ddd3,

title = "Excluding the fork and antifork",

abstract = "The fork is the tree obtained from the claw K1,3 by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs that do not contain the fork or antifork as induced subgraphs.",

keywords = "Antifork, Forbidden induced subgraph, Fork, Graph structure",

author = "Maria Chudnovsky and Linda Cook and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2020",

month = may,

doi = "10.1016/j.disc.2019.111786",

language = "English (US)",

volume = "343",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Excluding the fork and antifork

AU - Chudnovsky, Maria

AU - Cook, Linda

AU - Seymour, Paul

PY - 2020/5

Y1 - 2020/5

N2 - The fork is the tree obtained from the claw K1,3 by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs that do not contain the fork or antifork as induced subgraphs.

AB - The fork is the tree obtained from the claw K1,3 by subdividing one of its edges once, and the antifork is its complement graph. We give a complete description of all graphs that do not contain the fork or antifork as induced subgraphs.

KW - Antifork

KW - Forbidden induced subgraph

KW - Fork

KW - Graph structure

UR - https://www.scopus.com/pages/publications/85077927112

UR - https://www.scopus.com/pages/publications/85077927112#tab=citedBy

U2 - 10.1016/j.disc.2019.111786

DO - 10.1016/j.disc.2019.111786

M3 - Article

AN - SCOPUS:85077927112

SN - 0012-365X

VL - 343

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

M1 - 111786

ER -

Excluding the fork and antifork

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this