A reduction procedure for coloring perfect K4-free graphs

Alan Tucker

doi:10.1016/0095-8956(87)90019-0

A reduction procedure for coloring perfect K₄-free graphs

Alan Tucker

Applied Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

16 Scopus citations

Abstract

This paper presents an algorithmic proof of the validity of the Strong Perfect Graph Conjecture for graphs whose largest clique is a triangle. The proof leads to an O(n³) algorithm to 3-color such graphs. In the process, a method is presented to contract a perfect graph into a set of smaller perfect graphs that are (K₄-e)-free.

Original language	English
Pages (from-to)	151-172
Number of pages	22
Journal	Journal of Combinatorial Theory, Series B
Volume	43
Issue number	2
DOIs	https://doi.org/10.1016/0095-8956(87)90019-0
State	Published - Oct 1987

Access to Document

10.1016/0095-8956(87)90019-0

Cite this

@article{46832a0446434dc297a15f8160ec1082,

title = "A reduction procedure for coloring perfect K4-free graphs",

abstract = "This paper presents an algorithmic proof of the validity of the Strong Perfect Graph Conjecture for graphs whose largest clique is a triangle. The proof leads to an O(n3) algorithm to 3-color such graphs. In the process, a method is presented to contract a perfect graph into a set of smaller perfect graphs that are (K4-e)-free.",

author = "Alan Tucker",

year = "1987",

month = oct,

doi = "10.1016/0095-8956(87)90019-0",

language = "English",

volume = "43",

pages = "151--172",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

number = "2",

}

TY - JOUR

T1 - A reduction procedure for coloring perfect K4-free graphs

AU - Tucker, Alan

PY - 1987/10

Y1 - 1987/10

N2 - This paper presents an algorithmic proof of the validity of the Strong Perfect Graph Conjecture for graphs whose largest clique is a triangle. The proof leads to an O(n3) algorithm to 3-color such graphs. In the process, a method is presented to contract a perfect graph into a set of smaller perfect graphs that are (K4-e)-free.

AB - This paper presents an algorithmic proof of the validity of the Strong Perfect Graph Conjecture for graphs whose largest clique is a triangle. The proof leads to an O(n3) algorithm to 3-color such graphs. In the process, a method is presented to contract a perfect graph into a set of smaller perfect graphs that are (K4-e)-free.

UR - https://www.scopus.com/pages/publications/38249034005

U2 - 10.1016/0095-8956(87)90019-0

DO - 10.1016/0095-8956(87)90019-0

M3 - Article

AN - SCOPUS:38249034005

SN - 0095-8956

VL - 43

SP - 151

EP - 172

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

A reduction procedure for coloring perfect K₄-free graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this