๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A note on tolerance graph recognition

โœ Scribed by Ryan B. Hayward; Ron Shamir


Book ID
108110481
Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
201 KB
Volume
143
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.


๐Ÿ“œ SIMILAR VOLUMES


A Note on Graph Pebbling
โœ Andrzej Czygrinow; Glenn Hurlbert; H.A. Kierstead; William T. Trotter ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Springer Japan ๐ŸŒ English โš– 110 KB
A Note on Graph Colorings and Graph Poly
โœ Noga Alon; Michael Tarsi ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

A note on computing graph closures
โœ Jeremy P. Spinrad ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 153 KB

This note shows that the k-closure of a graph can be computed in time proportional to the size of the output, improving on previous O(n 3 ) algorithms.