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.