✦ LIBER ✦

Strong chromatic index of subset graphs

✍ Scribed by Quinn, Jennifer J.; Benjamin, Arthur T.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 115 KB
Volume: 24
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199703)23:3<267::aid-jgt8>3.0.co;2-n

No coin nor oath required. For personal study only.

✦ Synopsis

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph S m (k, l) is a bipartite graph whose vertices are the kand l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. We show that sq(S m (k, l)) = ( m l-k ) and that this number satisfies the strong chromatic index conjecture by Brualdi and Quinn for bipartite graphs. Further, we demonstrate that the conjecture is also valid for a more general family of bipartite graphs.

📜 SIMILAR VOLUMES

The strong chromatic index of C4-free gr

The strong chromatic index of C4-free graphs

✍ Mohammad Mahdian 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 1 views

Chromatic-index-critical graphs of even

Chromatic-index-critical graphs of even order

✍ Gr�newald, Stefan; Steffen, Eckhard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 1 views

A k-critical (multi-) graph G has maximum degree k, chromatic index χ (G) = k + 1, and χ (G -e) < k + 1 for each edge e of G. For each k ≥ 3, we construct k-critical (multi-) graphs with certain properties to obtain counterexamples to some well-known conjectures.

Game chromatic index of k-degenerate gra

Game chromatic index of k-degenerate graphs

✍ Leizhen Cai; Xuding Zhu 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

Improved bounds for the chromatic index

Improved bounds for the chromatic index of graphs and multigraphs

✍ Hakimi, S. Louis; Schmeichel, Edward F. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB 👁 2 views

We show that coloring the edges of a multigraph G in a particular order often leads to improved upper bounds for the chromatic index χ (G). Applying this to simple graphs, we significantly generalize recent conditions based on the core of G (i.e., the subgraph of G induced by the vertices of degree

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

Game chromatic number of outerplanar gra

Game chromatic number of outerplanar graphs

✍ Guan, D. J.; Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs.