로그인
ACTIVITIES
Preprints
Home > Activities > Basic Research > Preprints
    Title      l  Finding minimum clique capacity
    Author   l  Maria Chudnovsky, Sang-Il Oum, Paul Seymour
    Date   l  2009-09-21
    Category   l  ASARC-Preprint-09-25
    Download    l 1253493521_0.957902.pdf  
Abstract: Let C be a clique of a graph G. The capacity of C is dened to be (jV (G) n Cj + jDj)=2, where
D is the set of vertices in V (G) n C that have both a neighbour and a non-neighbour in C. We
give a polynomial-time algorithm to nd the minimum clique capacity in a graph G. This problem
arose as an open question in a 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.

Keyword

년도별 리스트보기 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008
File Title Authors Date Category
 On some first sign change problems of modular forms Seokho Jin 2014-11-28 ASARC-Preprint
14-10
 Geometric properties of projective manifolds of small degree Sijong Kwak, Jinhyung Park 2014-09-03 ASARC-Preprint
14-09
 ON ARITHMETIC PROPERTIES OF THE p-UNITS SOOGIL SEO 2014-08-29 ASARC-Preprint
14-08
 Geometric properities of projective manifolds of small degree Sijong Kwak and Jinhyung Park 2014-03-06 ASARC-Preprint
14-07
 Periodic Hamiltonian flows with almost minimality conditions Jin Hong Kim 2014-02-28 ASARC-Preprint
14-06
 ON THE REGULARIZED IMAGINARY DOI-NAGANUMA LIFTING SEOKHO JIN* AND SUBONG LIM 2014-02-27 ASARC-Preprint
14-05
 THE NUMBER OF B3-SETS OF A GIVEN CARDINALITY DOMINGOS DELLAMONICA JR., YOSHIHARU KOHAYAKAWA, SANG JUNE LEE, VOJTECH RODL, AND WOJCIECH SAMOTIJ 2014-02-10 ASARC-Preprint
14-04
 On a generalization of Hirzebruch's theorem to Bott towers Jin Hong Kim 2014-02-06 ASARC-Preprint
14-03
 NUMBER OF NODAL DOMAINS OF EIGENFUNCTIONS ON NON-POSITIVELY CURVED SURFACES WITH CONCAVE BOUNDARY JUNEHYUK JUNG AND STEVE ZELDITCH 14-01-21 ASARC-Preprint
2014-02
 Quantitative quantum ergodicity and the nodal domains of Maass-Hecke cusp forms Junehyuk Jung 2014-01-10 ASARC-Preprint
14-01
 Fourier-Mukai transformation on algebraic cobordism Anandam Banerjee, Thomas Hudson 2013-12-09 ASARC-Preprint
13-13
 On numerical equivalence for algebraic cobordism Anandam Banerjee, Jinhyun Park 2013-12-09 ASARC-Preprint
13-12
 UNIVERSALITY OF RANDOM GRAPHS FOR GRAPHS OF MAXIMUM DEGREE TWO JEONG HAN KIM AND SANG JUNE LEE 2013-10-24 ASARC-Prepint
13-11
 NUMBER OF NODAL DOMAINS AND SINGULAR POINTS OF EIGENFUNCTIONS OF NEGATIVELY CURVED SURFACES WITH AN ISOMETRIC INVOLUTION JUNEHYUK JUNG AND STEVE ZELDITCH 2013-10-21 ASARC-Prepint
13-10
 ON THE NUMBER OF B_h-SETS DOMINGOS DELLAMONICA JR., YOSHIHARU KOHAYAKAWA, SANG JUNE LEE, VOJTECH RODL, AND WOJCIECH SAMOTIJ 2013-10-08 ASARC-Prepint
13-09
 A Thom-Porteous formula for connective K-theory using algebraic cobordism THOMAS HUDSON 2013-10-02 ASARC-Prepint
13-08
 Semi-topologization in motivic homotopy theory and applications Amalendu Krishna and Jinhyun Park 2013-09-30 ASARC-Prepint
13-07
 ON THE TATE MODULE OF A NUMBER FIELD SOOGIL 2013-09-12 ASARC-Prepint
13-06
 ON THE CONJECTURES OF GROSS AND LEOPOLDT SOOGIL SEO 2013-09-12 ASARC-Prepint
13-05
 On the free rank of abelian groups acting freely on products of spheres Jin Hong Kim 2013-09-06 ASARC-Prepint
13-04
123456