✦ LIBER ✦

The skew chromatic index of a graph

✍ Scribed by Marsha F Foregger

Publisher: Elsevier Science
Year: 1984
Tongue: English
Weight: 594 KB
Volume: 49
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(84)90148-1

No coin nor oath required. For personal study only.

✦ Synopsis

We define a skew edge coloring of a graph to be a set of two edge colorings such that no two edges are assigned the same unordered pair of colors. The skew chromatic index s(G) is the minimum number of colors required for a skew edge coloring of G. We show that this concept is closely related to that of skew Room squares and use this relation to prove that s(G) is at most o(G)+4. We also find better upper bounds for s(G) when G is cyclic, cubic, or bipartite. In particular we use a construction involving Latin squares to show that if G is complete bipartite of order 2n, s(G) is hounded above by roughly 3n/2. * This paper is drawn from the author's Ph.D. thesis, written under the supervision of Professor R.A.

📜 SIMILAR VOLUMES

A Bound on the Strong Chromatic Index of

A Bound on the Strong Chromatic Index of a Graph

✍ Michael Molloy; Bruce Reed 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 695 KB

We show that the strong chromatic index of a graph with maximum degree 2 is at most (2&=) 2 2 , for some =>0. This answers a question of Erdo s and Nes etr il. 1997 Academic Press ## 1. Introduction A strong edge-colouring of a (simple) graph, G, is a proper edge-colouring of G with the added res

A construction of chromatic index critic

A construction of chromatic index critical graphs

✍ Hian Poh Yap 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

## Abstract We prove that if __K__ is an undirected, simple, connected graph of even order which is of class one, regular of degree __p__ ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph __G__ obtained from __K__ by splitting any vertex is __p

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.

The chromatic index of complete multipar

The chromatic index of complete multipartite graphs

✍ D. G. Hoffman; C. A. Rodger 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

## Abstract We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index.

The chromatic index of graphs with a spa

The chromatic index of graphs with a spanning star

✍ Mike Plantholt 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 468 KB 👁 1 views

## Abstract Vizing's Theorem states that any graph __G__ has chromatic index either the maximum degree Δ(__G__) or Δ(__G__) + 1. If __G__ has 2~s~ + 1 points and Δ(__G__) = 2s, a well‐known necessary condition for the chromatic index to equal 2~s~ is that __G__ have at most 2s^2^ lines. Hilton conj

Strong chromatic index of subset graphs

✍ Quinn, Jennifer J.; Benjamin, Arthur T. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

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 ar