Solution of three problems of Cornuéjols

Maria Chudnovsky; Paul Seymour

doi:10.1016/j.jctb.2007.05.004

Solution of three problems of Cornuéjols

Mathematics

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

Abstract

A graph is balanced if it is bipartite and every induced cycle has length divisible by four. In his book, Gérard Cornuéjols proposed a number of open questions, offering $5000 for the solution of any of them. Here we solve three of them, about balanced graphs.

Original language	English (US)
Pages (from-to)	116-135
Number of pages	20
Journal	Journal of Combinatorial Theory. Series B
Volume	98
Issue number	1
DOIs	https://doi.org/10.1016/j.jctb.2007.05.004
State	Published - Jan 2008

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2007.05.004

Cite this

@article{de11894098c44d5e86774a15f8687878,

title = "Solution of three problems of Cornu{\'e}jols",

abstract = "A graph is balanced if it is bipartite and every induced cycle has length divisible by four. In his book, G{\'e}rard Cornu{\'e}jols proposed a number of open questions, offering \$5000 for the solution of any of them. Here we solve three of them, about balanced graphs.",

author = "Maria Chudnovsky and Paul Seymour",

note = "Funding Information: 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow at Princeton University. 2 Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.",

year = "2008",

month = jan,

doi = "10.1016/j.jctb.2007.05.004",

language = "English (US)",

volume = "98",

pages = "116--135",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Solution of three problems of Cornuéjols

AU - Chudnovsky, Maria

AU - Seymour, Paul

N1 - Funding Information: 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow at Princeton University. 2 Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.

PY - 2008/1

Y1 - 2008/1

N2 - A graph is balanced if it is bipartite and every induced cycle has length divisible by four. In his book, Gérard Cornuéjols proposed a number of open questions, offering $5000 for the solution of any of them. Here we solve three of them, about balanced graphs.

AB - A graph is balanced if it is bipartite and every induced cycle has length divisible by four. In his book, Gérard Cornuéjols proposed a number of open questions, offering $5000 for the solution of any of them. Here we solve three of them, about balanced graphs.

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

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

U2 - 10.1016/j.jctb.2007.05.004

DO - 10.1016/j.jctb.2007.05.004

M3 - Article

AN - SCOPUS:36048939129

SN - 0095-8956

VL - 98

SP - 116

EP - 135

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Solution of three problems of Cornuéjols

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this