Premium
A counterexample to the rank‐coloring conjecture
Author(s) -
Alon N.,
Seymour P. D.
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130413
Subject(s) - mathematics , counterexample , combinatorics , rank (graph theory) , conjecture , chromatic scale , adjacency matrix , graph , discrete mathematics
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.