On the function ``sandwiched'' between \(\alpha(G)\) and \(\bar\chi (G)\)
The electronic journal of combinatorics, Tome 4 (1997) no. 1
A new function of a graph $G$ is presented. Say that a matrix $B$ that is indexed by vertices of $G$ is feasible for $G$ if it is real, symmetric and $I \le B \le I + A(G),$ where $I$ is the identity matrix and $A(G)$ is the adjacency matrix of $G$. Let $\cal B(G)$ be the set of all feasible matrices for $G$, and let $\overline{\chi}(G)$ be the smallest number of cliques that cover the vertices of $G$. We show that $$ \alpha(G) \le \min \{ {\rm rank }(B)\ \vert B \in \cal B(G)\} \le \overline{\chi}(G) $$ and that $\alpha(G)= \min \{\ {\rm rank }(B)\ \vert B \in \cal B(G)\}$ implies $ \alpha(G)=\overline{\chi}(G).$
@article{10_37236_1304,
author = {V. Y. Dobrynin},
title = {On the function ``sandwiched'' between {\(\alpha(G)\)} and \(\bar\chi {(G)\)}},
journal = {The electronic journal of combinatorics},
year = {1997},
volume = {4},
number = {1},
doi = {10.37236/1304},
zbl = {0885.05070},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1304/}
}
V. Y. Dobrynin. On the function ``sandwiched'' between \(\alpha(G)\) and \(\bar\chi (G)\). The electronic journal of combinatorics, Tome 4 (1997) no. 1. doi: 10.37236/1304
Cité par Sources :