✦ LIBER ✦

On the Computational Complexity of the Forcing Chromatic Number

✍ Scribed by Harary, Frank; Slany, Wolfgang; Verbitsky, Oleg

Book ID: 118180698
Publisher: Society for Industrial and Applied Mathematics
Year: 2007
Tongue: English
Weight: 284 KB
Volume: 37
Category: Article
ISSN: 0097-5397
DOI: 10.1137/050641594

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Computational complexity of (2,2) path c

Computational complexity of (2,2) path chromatic number problem

✍ Yuan Jinjiang 📂 Article 📅 1995 🏛 SP Editorial Committee of Applied Mathematics - A 🌐 English ⚖ 259 KB

On the complexity of the circular chroma

On the complexity of the circular chromatic number

✍ H. Hatami; R. Tusserkani 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 1 views

## Abstract Circular chromatic number, χ~__c__~ is a natural generalization of chromatic number. It is known that it is **NP**‐hard to determine whether or not an arbitrary graph __G__ satisfies χ(__G__)=χ~__c__~(__G__). In this paper we prove that this problem is **NP**‐hard even if the chromatic

On the chromatic forcing number of a ran

On the chromatic forcing number of a random graph

✍ Colin McDiarmid 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 549 KB

A note on the complexity of the chromati

A note on the complexity of the chromatic number problem

✍ E.L. Lawler 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 285 KB

Acyclic graph coloring and the complexit

Acyclic graph coloring and the complexity of the star chromatic number

✍ David R. Guichard 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB

## Abstract Star chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, “When is χ\* < χ?” We show that χ\* < χ if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not i

On the mean chromatic number

✍ Martin Anthony 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 209 KB

The mean chromatic number of a graph is a measure of the expected performance of the greedy vertex-colouring algorithm when each ordering of the vertices is equally likely. Some results on the value of the mean chromatic number and its asymptotic behaviour are presented.