Premium
Rank and chromatic number of a graph
Author(s) -
Kotlov Andrei˘
Publication year - 1997
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/(sici)1097-0118(199709)26:1<1::aid-jgt1>3.0.co;2-n
Subject(s) - combinatorics , mathematics , windmill graph , chromatic scale , friendship graph , graph , critical graph , adjacency matrix , wheel graph , discrete mathematics , line graph , graph power
It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185–189) that the number of vertices in a twin‐free graph is $O((\sqrt{2})^r)$ where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is $o(\Delta ^r)$ where $\Delta = 4/3 < \sqrt{2}$. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 1–8, 1997