𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An edge coloring problem for graph products

✍ Scribed by Faudree, R. J.; Gy�rf�s, Andr�as; Schelp, R. H.

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
315 KB
Volume
23
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

The edges of the Cartesian product of graphs G x H a r e to be colored with the condition that all rectangles, i.e., K2 x K2 subgraphs, must be colored with four distinct colors.

The minimum number of colors in such colorings is determined for all pairs of graphs except when G is 5-chromatic and H is 4-or 5-chromatic.

📜 SIMILAR VOLUMES

Deferred-query: An efficient approach fo
Deferred-query: An efficient approach for some problems on interval graphs
✍ Chang, Maw-Shang; Peng, Sheng-Lung; Liaw, Jenn-Liang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 1 views

This paper introduces the idea of a deferred-query approach to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit, and maximum matching problems on interval graphs given n endpoint-sorted intervals. The previous best-known algorithms run in O(

Clustering analysis for graphs with mult
Clustering analysis for graphs with multiweighted edges: A unified approach to the threshold problem
✍ Goetschel, Roy 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 494 KB 👁 1 views

Multivalent relations, inferred as relationships with an added dimension of discernment, are realized as weighted graphs with multivalued edges. A unified treatment of the threshold problem is discussed and a reliability measure is produced to judge various partitions. 'R+ represents the non-negati

A simpleO(n2) algorithm for the all-pair
A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
✍ Mirchandani, Prakash 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 1 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a