𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A counterexample to the Alon-Saks-Seymour conjecture and related problems

✍ Scribed by Hao Huang, Benny Sudakov

Book ID
113046145
Publisher
Springer-Verlag
Year
2012
Tongue
English
Weight
226 KB
Volume
32
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A counterexample to the rank-coloring co
A counterexample to the rank-coloring conjecture
✍ N. Alon; P. D. Seymour πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 140 KB

It has been conjectured by C. van Nuffelen that the chromatic number of any graph with at least one edge does not exceed the rank of its adjacency matrix. We give a counterexample, with chromatic number 32 and with an adjacency matrix of rank 29.

A counterexample to the bold conjecture
A counterexample to the bold conjecture
✍ Sakuma, Tadashi πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 83 KB πŸ‘ 1 views

A pair of vertices (x, y) of a graph G is an Ο‰-critical pair if Ο‰(G + xy) > Ο‰(G), where G + xy denotes the graph obtained by adding the edge xy to G and Ο‰(H) is the clique number of H. The Ο‰-critical pairs are never edges in G. A maximal stable set S of G is called a forced color class of G if S mee