✦ LIBER ✦

Semistrong edge coloring of graphs

✍ Scribed by András Gyárfás; Alice Hubenko

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 80 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20061

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Weakening the notion of a strong (induced) matching of graphs, in this paper, we introduce the notion of a semistrong matching. A matching M of a graph G is called semistrong if each edge of M has a vertex, which is of degree one in the induced subgraph G[M]. We strengthen earlier results by showing that for the subset graphs and for the Kneser graphs the sizes of the maxima of the strong and semistrong matchings are equal and so are the strong and semistrong chromatic indices. Similar properties are conjectured for the n‐dimensional cube. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 39–47, 2005

📜 SIMILAR VOLUMES

Edge-Coloring Bipartite Graphs

✍ Ajai Kapoor; Romeo Rizzi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 65 KB

Given a bipartite graph G with n nodes, m edges, and maximum degree ⌬, we Ž . find an edge-coloring for G using ⌬ colors in time T q O m log ⌬ , where T is the time needed to find a perfect matching in a k-regular bipartite graph with Ž . O m edges and k F ⌬. Together with best known bounds for T th

Optimal edge coloring of large graphs

✍ G�mez, J.; Escudero, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 3 views

Most of the general families of large considered graphs in the context of the so-called (⌬, D) problem-that is, how to obtain graphs with maximum order, given their maximum degree ⌬ and their diameter D-known up to now for any value of ⌬ and D, are obtained as product graphs, compound graphs, and ge

Acyclic edge coloring of 2-degenerate gr

Acyclic edge coloring of 2-degenerate graphs

✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 280 KB 👁 1 views

## Abstract An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__′(__G__). A graph is

Optimal acyclic edge-coloring of cubic g

Optimal acyclic edge-coloring of cubic graphs

✍ Lars Døvling Andersen; Edita Máčajová;; Ján Mazák 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

An __acyclic edge‐coloring__ of a graph is a proper edge‐coloring such that the subgraph induced by the edges of any two colors is acyclic. The __acyclic chromatic index__ of a graph __G__ is the smallest number of colors in an acyclic edge‐coloring of __G__. We prove that the acyclic chromatic inde

Coloring edges of embedded graphs

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

In this paper, we prove that any graph G with maximum degree ÁG ! 11 p 49À241AEa2, which is embeddable in a surface AE of characteristic 1AE 1 and satis®es jVGj b 2ÁGÀ5À2 p 6ÁG, is class one.

Acyclic edge colorings of graphs

✍ Noga Alon; Benny Sudakov; Ayal Zaks 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract A proper coloring of the edges 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 __a′__(__G__), is the least number of colors in an acyclic edge coloring of __G__. For certain graphs __G__, __a′__(_