Odd holes in bull-free graphs∗

Maria Chudnovsky; Vaidy Sivaraman

doi:10.1137/17M1131301

Odd holes in bull-free graphs^∗

Maria Chudnovsky, Vaidy Sivaraman

Mathematics

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

7 Scopus citations

Abstract

The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges).

Original language	English (US)
Pages (from-to)	951-955
Number of pages	5
Journal	SIAM Journal on Discrete Mathematics
Volume	32
Issue number	2
DOIs	https://doi.org/10.1137/17M1131301
State	Published - 2018

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Algorithm
Bull-free
Odd hole

Access to Document

10.1137/17M1131301

Cite this

@article{7debeb7e003f4984b000830f34a1d682,

title = "Odd holes in bull-free graphs∗ ",

abstract = "The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges).",

keywords = "Algorithm, Bull-free, Odd hole",

author = "Maria Chudnovsky and Vaidy Sivaraman",

note = "Publisher Copyright: {\textcopyright} 2018 Society for Industrial and Applied Mathematics.",

year = "2018",

doi = "10.1137/17M1131301",

language = "English (US)",

volume = "32",

pages = "951--955",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

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

number = "2",

}

TY - JOUR

T1 - Odd holes in bull-free graphs∗

AU - Chudnovsky, Maria

AU - Sivaraman, Vaidy

PY - 2018

Y1 - 2018

N2 - The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges).

AB - The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges).

KW - Algorithm

KW - Bull-free

KW - Odd hole

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

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

U2 - 10.1137/17M1131301

DO - 10.1137/17M1131301

M3 - Article

AN - SCOPUS:85049566857

SN - 0895-4801

VL - 32

SP - 951

EP - 955

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -