Finding minimum clique capacity

Maria Chudnovsky; Sang Il Oum; Paul Seymour

doi:10.1007/s00493-012-2891-9

Finding minimum clique capacity

Maria Chudnovsky, Sang Il Oum, Paul Seymour

Mathematics

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

Abstract

Let C be a clique of a graph G. The capacity of C is defined to be ({pipe}V (G)/C{pipe}+{pipe}D{pipe})/2, where D is the set of vertices in V (G)/C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger's conjecture.

Original language	English (US)
Pages (from-to)	283-287
Number of pages	5
Journal	Combinatorica
Volume	32
Issue number	3
DOIs	https://doi.org/10.1007/s00493-012-2891-9
State	Published - Apr 2012

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-012-2891-9

Cite this

@article{2742cc907ac148d697e0243ca3f7b4cd,

title = "Finding minimum clique capacity",

abstract = "Let C be a clique of a graph G. The capacity of C is defined to be ({pipe}V (G)/C{pipe}+{pipe}D{pipe})/2, where D is the set of vertices in V (G)/C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger's conjecture.",

author = "Maria Chudnovsky and Oum, {Sang Il} and Paul Seymour",

note = "Funding Information: ∗ Supported by NSF grants DMS-1001091 and IIS-1117631. †Supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2011-0011653) and a TJ Park Junior Faculty Fellowship. ‡ Supported by ONR grant N00014-10-1-0680 and NSF grant DMS-0901075.",

year = "2012",

month = apr,

doi = "10.1007/s00493-012-2891-9",

language = "English (US)",

volume = "32",

pages = "283--287",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

T1 - Finding minimum clique capacity

AU - Chudnovsky, Maria

AU - Oum, Sang Il

AU - Seymour, Paul

N1 - Funding Information: ∗ Supported by NSF grants DMS-1001091 and IIS-1117631. †Supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2011-0011653) and a TJ Park Junior Faculty Fellowship. ‡ Supported by ONR grant N00014-10-1-0680 and NSF grant DMS-0901075.

PY - 2012/4

Y1 - 2012/4

N2 - Let C be a clique of a graph G. The capacity of C is defined to be ({pipe}V (G)/C{pipe}+{pipe}D{pipe})/2, where D is the set of vertices in V (G)/C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger's conjecture.

AB - Let C be a clique of a graph G. The capacity of C is defined to be ({pipe}V (G)/C{pipe}+{pipe}D{pipe})/2, where D is the set of vertices in V (G)/C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger's conjecture.

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

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

U2 - 10.1007/s00493-012-2891-9

DO - 10.1007/s00493-012-2891-9

M3 - Article

AN - SCOPUS:84865810649

SN - 0209-9683

VL - 32

SP - 283

EP - 287

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

Finding minimum clique capacity

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this