The strong chromatic number of partial triple systems

Charles J. Colbourn; Dieter Jungnickel; Alexander Rosa

doi:10.1016/0166-218X(88)90039-X

The strong chromatic number of partial triple systems

Charles J. Colbourn, Dieter Jungnickel, Alexander Rosa

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

6 Scopus citations

Abstract

A strong colouring of a hypergraph is an assignment of colours to its vertices so that no two vertices in a hyperedge have the same colour. We establish that strong colouring of partial triple systems is NP-complete, even when the number of colours is any fixed k≥3. In contrast, an efficient algorithm is given for strong colouring of maximal partial triple systems. Observations in this algorithm underpin a complete determination of the spectrum of strong chromatic numbers for maximal partial triple systems.

Original language	English (US)
Pages (from-to)	31-38
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	20
Issue number	1
DOIs	https://doi.org/10.1016/0166-218X(88)90039-X
State	Published - May 1988
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/0166-218X(88)90039-X

Cite this

@article{2d49b230f8ce466f9a5cb8e1bea08145,

title = "The strong chromatic number of partial triple systems",

abstract = "A strong colouring of a hypergraph is an assignment of colours to its vertices so that no two vertices in a hyperedge have the same colour. We establish that strong colouring of partial triple systems is NP-complete, even when the number of colours is any fixed k≥3. In contrast, an efficient algorithm is given for strong colouring of maximal partial triple systems. Observations in this algorithm underpin a complete determination of the spectrum of strong chromatic numbers for maximal partial triple systems.",

author = "Colbourn, {Charles J.} and Dieter Jungnickel and Alexander Rosa",

year = "1988",

month = may,

doi = "10.1016/0166-218X(88)90039-X",

language = "English (US)",

volume = "20",

pages = "31--38",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - The strong chromatic number of partial triple systems

AU - Colbourn, Charles J.

AU - Jungnickel, Dieter

AU - Rosa, Alexander

PY - 1988/5

Y1 - 1988/5

N2 - A strong colouring of a hypergraph is an assignment of colours to its vertices so that no two vertices in a hyperedge have the same colour. We establish that strong colouring of partial triple systems is NP-complete, even when the number of colours is any fixed k≥3. In contrast, an efficient algorithm is given for strong colouring of maximal partial triple systems. Observations in this algorithm underpin a complete determination of the spectrum of strong chromatic numbers for maximal partial triple systems.

AB - A strong colouring of a hypergraph is an assignment of colours to its vertices so that no two vertices in a hyperedge have the same colour. We establish that strong colouring of partial triple systems is NP-complete, even when the number of colours is any fixed k≥3. In contrast, an efficient algorithm is given for strong colouring of maximal partial triple systems. Observations in this algorithm underpin a complete determination of the spectrum of strong chromatic numbers for maximal partial triple systems.

UR - http://www.scopus.com/inward/record.url?scp=0024011254&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024011254&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(88)90039-X

DO - 10.1016/0166-218X(88)90039-X

M3 - Article

AN - SCOPUS:0024011254

SN - 0166-218X

VL - 20

SP - 31

EP - 38

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -

The strong chromatic number of partial triple systems

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this