Conditions for $\beta$-perfectness

J.C.M. Keijsper, M. Tewes

    Research output: Book/ReportReportOther research output

    25 Downloads (Pure)

    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 languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente, Department of Applied Mathematics
    Publication statusPublished - 2000

    Publication series

    Name
    PublisherDepartment 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.