\(\beta\)-perfect graphs (Q1924134): Difference between revisions

Let \(\delta(G)\) and \(\chi(G)\) denote the minimum degree and chromatic number of the simple graph \(G\) respectively. Define \(\beta(G)=1+\max\{\delta(H)\}\) where \(H\) varies over all the induced subgraphs of \(G\). It is clear that \(\beta(G)\leq \chi(G)\) and \(G\) is said to be \(\beta\)-perfect if \(\beta(H)= \chi(H)\) for each induced subgraph \(H\) of \(G\). A number of analogs are drawn between \(\beta\)-perfect and perfect graphs and some special classes of \(\beta\)-perfect graphs are introduced. Finally, the authors show that the greedy algorithm can be used to color a graph \(G\) with no even cycles using at most \(2(\chi(G)-1)\) colors.