2
$\begingroup$

The perfect graphs are generally defined as those graphs whose every induced subgraph has its chromatic number equal to its clique number.

Now,are there some examples where the clique number of graph equals its chromatic number but some induced subgraph has different clique and chromatic numbers. If so, then for what class of graphs, does the equivalence of chromatic and clique numbers for graphs implies their equivalence for every induced subgraph. Complete graphs, their line graphs, bipartite graphs, their line graphs are such examples.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Trivially, any given graph $H$ is an induced subgraph of another graph $G$ such that the chromatic number and the clique number of $G$ are both equal to the chromatic number of $H$. $\endgroup$
    – bof
    Commented Dec 19, 2019 at 23:26

1 Answer 1

Reset to default
2
$\begingroup$

No, the definition of perfect graphs is perfect! and cannot be weakened. For example, consider the graph as shown in this picture. Here five $5$ cliques are arranged in the form of a pentagon.

A pentagon of five cliques

Here Clique size is $5$. Here, let the five color classes of vertices be: $[A,N,R,K,G],[E,Q,T,L,I],[B,O,S,H],[C,M,F],[D,P,J]$. This gives us a five coloring of the graph. But, note that the induced subgraph formed by the vertices $P,C,D,H,M$ is an odd hole (chordless cycle of length $5$); so that the graph is not perfect. Though my guess is that the condition could be weakened for vertex-transitive perfect graphs.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .