✦ LIBER ✦

A note on the complexity of the chromatic number problem

✍ Scribed by E.L. Lawler

Book ID: 113161860
Publisher: Elsevier Science
Year: 1976
Tongue: English
Weight: 285 KB
Volume: 5
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(76)90065-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A note on the star chromatic number

✍ J. A. Bondy; Pavol Hell 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB 👁 1 views

## Abstract A. Vince introduced a natural generalization of graph coloring and proved some basic facts, revealing it to be a concept of interest. His work relies on continuous methods. In this note we make some simple observations that lead to a purely combinatorial treatment. Our methods yield sho

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

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 Computational Complexity of the F

On the Computational Complexity of the Forcing Chromatic Number

✍ Harary, Frank; Slany, Wolfgang; Verbitsky, Oleg 📂 Article 📅 2007 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 284 KB

Note on the Number of Distinct Chromatic

Note on the Number of Distinct Chromaticities

✍ MACADAM, D. L. 📂 Article 📅 1947 🏛 Optical Society of America ⚖ 624 KB

A note on the line-distinguishing chroma

A note on the line-distinguishing chromatic number and the chromatic index of a graph

✍ N. Zagaglia Salvi 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let λ(__G__) be the line‐distinguishing chromatic number and __x__′(__G__) the chromatic index of a graph __G__. We prove the relation λ(__G__) ≥ __x__′(__G__), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.