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.

$\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
    Dec 19 '19 at 23:26
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.