Colouring steiner quadruple systems

Charles J. Colbourn; Marlene J. Colbourn; Kevin T. Phelps; Vojtěch Rödl

doi:10.1016/0166-218X(82)90068-3

Colouring steiner quadruple systems

Charles J. Colbourn
, Marlene J. Colbourn
, Kevin T. Phelps
, Vojtěch Rödl

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

7 Scopus citations

Abstract

An algorithm is described which finds a proper 2-colouring of a Steiner quadruple system if one exists; the time required by this method is polynomial. By way of contrast, 2-colouring a partial Steiner quadruple system is shown to be NP-complete.

Original language	English (US)
Pages (from-to)	103-111
Number of pages	9
Journal	Discrete Applied Mathematics
Volume	4
Issue number	2
DOIs	https://doi.org/10.1016/0166-218X(82)90068-3
State	Published - Apr 1982
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/0166-218X(82)90068-3

Cite this

@article{30e40364b3d142f19a37336d25179f6e,

title = "Colouring steiner quadruple systems",

abstract = "An algorithm is described which finds a proper 2-colouring of a Steiner quadruple system if one exists; the time required by this method is polynomial. By way of contrast, 2-colouring a partial Steiner quadruple system is shown to be NP-complete.",

author = "Colbourn, \{Charles J.\} and Colbourn, \{Marlene J.\} and Phelps, \{Kevin T.\} and Vojt{\v e}ch R{\"o}dl",

year = "1982",

month = apr,

doi = "10.1016/0166-218X(82)90068-3",

language = "English (US)",

volume = "4",

pages = "103--111",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Colouring steiner quadruple systems

AU - Colbourn, Charles J.

AU - Colbourn, Marlene J.

AU - Phelps, Kevin T.

AU - Rödl, Vojtěch

PY - 1982/4

Y1 - 1982/4

N2 - An algorithm is described which finds a proper 2-colouring of a Steiner quadruple system if one exists; the time required by this method is polynomial. By way of contrast, 2-colouring a partial Steiner quadruple system is shown to be NP-complete.

AB - An algorithm is described which finds a proper 2-colouring of a Steiner quadruple system if one exists; the time required by this method is polynomial. By way of contrast, 2-colouring a partial Steiner quadruple system is shown to be NP-complete.

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

UR - https://www.scopus.com/pages/publications/49049137133#tab=citedBy

U2 - 10.1016/0166-218X(82)90068-3

DO - 10.1016/0166-218X(82)90068-3

M3 - Article

SN - 0166-218X

VL - 4

SP - 103

EP - 111

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -

Colouring steiner quadruple systems

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this