𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of chromatic strength and chromatic edge strength

✍ Scribed by Dániel Marx

Publisher
Springer
Year
2006
Tongue
English
Weight
341 KB
Volume
14
Category
Article
ISSN
1016-3328

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Edge-face chromatic number and edge chro
Edge-face chromatic number and edge chromatic number of simple plane graphs
✍ Rong Luo; Cun-Quan Zhang 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

## Abstract Given a simple plane graph __G__, an edge‐face __k__‐coloring of __G__ is a function ϕ : __E__(__G__) ∪ __F__(G) →  {1,…,__k__} such that, for any two adjacent or incident elements __a__, __b__ ∈ __E__(__G__) ∪ __F__(__G__), ϕ(__a__) ≠ ϕ(__b__). Let χ~e~(__G__), χ~ef~(__G__), and Δ(__G_

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

Acyclic edge chromatic number of outerpl
Acyclic edge chromatic number of outerplanar graphs
✍ Jian-Feng Hou; Jian-Liang Wu; Gui-Zhen Liu; Bin Liu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB

## Abstract A proper edge coloring of a graph __G__ is called acyclic if there is no 2‐colored cycle in __G__. The acyclic edge chromatic number of __G__, denoted by χ(__G__), is the least number of colors in an acyclic edge coloring of __G__. In this paper, we determine completely the acyclic edge

On the Size of Edge Chromatic Critical G
On the Size of Edge Chromatic Critical Graphs
✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 85 KB

In this paper, by applying the discharging method, we prove that if