Conditions for $\beta$-perfectness

J.C.M. Keijsper; M. Tewes

Conditions for $\beta$-perfectness

J.C.M. Keijsper, M. Tewes

Research output: Book/Report › Report › Other research output

47 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 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

Access to Document

Cite this

@book{1365452d428c42b4a36864efdc5a542a,

title = "Conditions for $\beta$-perfectness",

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).",

keywords = "EWI-3357, MSC-05C75, MSC-05C15, IR-65724",

author = "J.C.M. Keijsper and M. Tewes",

note = "Imported from MEMORANDA ",

year = "2000",

language = "Undefined",

publisher = "University of Twente, Department of Applied Mathematics",

number = "1537",

}

TY - BOOK

T1 - Conditions for $\beta$-perfectness

AU - Keijsper, J.C.M.

AU - Tewes, M.

N1 - Imported from MEMORANDA

PY - 2000

Y1 - 2000

N2 - 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).

AB - 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).

KW - EWI-3357

KW - MSC-05C75

KW - MSC-05C15

KW - IR-65724

M3 - Report

BT - Conditions for $\beta$-perfectness

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -