Abstract
A $\beta$-perfect graph is a simple graph $G$ such that $\chi(G')=\beta(G')$ for every induced subgraph $G'$ of $G$, where $\chi(G')$ is the chromatic number of $G'$, and $\beta(G')$ is defined as the maximum over all induced subgraphs $H$ of $G'$ of the minimum vertex degree in $H$. The vertices of a $\beta$-perfect graph $G$ can be coloured with $\chi(G)$ colours in polynomial time (greedily).
| Original language | Undefined |
|---|---|
| Place of Publication | Enschede |
| Publisher | University of Twente, Department of Applied Mathematics |
| Publication status | Published - 2000 |
Publication series
| Name | |
|---|---|
| Publisher | Department of Applied Mathematics, University of Twente |
| No. | 1537 |
| ISSN (Print) | 0169-2690 |
Keywords
- EWI-3357
- MSC-05C75
- MSC-05C15
- IR-65724
Cite this
Keijsper, J. C. M., & Tewes, M. (2000). Conditions for $\beta$-perfectness. Enschede: University of Twente, Department of Applied Mathematics.