Questions tagged [perfect-graph]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers

A variant of the Maximum Weight Clique problem

I am trying to solve a problem that I could reduce to the following: Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{...
Pawan Aurora's user avatar
6 votes
1 answer

Intersection models for weakly chordal graphs?

Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :) Among the many known classes of perfect graphs, there ...
NisaiVloot's user avatar
  • 1,292
7 votes
1 answer

Chromatic number of G+v where G is a cograph

Cograph is a well-know graph that does not have induced $P_4$. My questions are about determining the chromatic number of graphs in the class cograph+v. Notations: Denote by $\chi(G)$ the chromatic ...
Peng Zhang's user avatar
  • 1,443
5 votes
0 answers

Testbed of perfect graphs

Is there a publicly available testbed of perfect graphs? Ideally, the number of vertices should be 100 or more.
Austin Buchanan's user avatar