Premium
On graphs with polynomially solvable maximum‐weight clique problem
Author(s) -
Balas Egon,
Yu Chang Sung
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190206
Subject(s) - combinatorics , mathematics , clique , clique problem , clique graph , discrete mathematics , upper and lower bounds , graph , block graph , clique sum , split graph , chordal graph , line graph , 1 planar graph , graph power , mathematical analysis
We give a new bound on the number of maximal cliques in a graph, along with a bound on the length of odd antiholes that the graph can contain. Based on these bounds we then identify a family of graphs with polynomially solvable maximum weight clique problem, using the edgebicoloring approach developed in a recent paper by Balas, Chvatal, and Nesetril.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom