It was also asked in this question, but received no answer.
We can represent a graph $G(V,E)$ with it's adjacency matrix $A \in \{0,1\}^{|V| \times |V|}$, where $a_{ij}=1$ implies vertices $v_i,v_j$ are adjacent. There is another representation as $A \in \{0,1\}^{|V| \times |E|}$, where $a_{ij}=1$ implies edge-$j$ is incident on $v_i$ (this is usually used for hypergraphs, but I decided to included it just in case it might be relevant).
Let us focus on the first representation, what is the notion of chromatic number of a graph in this case? I couldn't find a standard/usual notion.
Edit:
To clarify, I'm not asking how to find a vertex coloring with as few as color as possible (or how to get the chromatic number).
What I'm asking is, is there something that can be taken as a vertex coloring/chromatic number.
For example, say $\exists w:w^TA=w$, then we take $|w|$ which would gives us the chromatic number. I'm curious if there is such a thing like this $w$, not how to compute $w$.
The statement above is of course, pure gibberish.
Best Answer
I want to nitpick and say (again, since I've said it in the comments) that the notion of chromatic number doesn't change. It doesn't matter how we represent a graph; we still define chromatic number in the same way.
But it is a legitimate question to ask whether we can express this notion in terms of the matrix representation of a graph. (Then it would be a legitimate question to ask whether this is useful; I don't think it usually is, but there might be exceptions.)
Here is a way to do it in terms of the $n \times m$ incidence matrix (which I'll call $B$ to distinguish it from the $n \times n$ adjacency matrix $A$). Here, $n$ denotes the number of vertices and $m$ denotes the number of edges. I'll write $1_{a \times b}$ to denote the matrix (or row vector, when $a=1$) where all entries are $1$.
We can think of a $k$-coloring of $G$ as a matrix $X \in \{0,1\}^{k \times n}$ where $x_{ij}=1$ implies color $i$ is used on vertex $j$. To ensure that every vertex gets a color, we want every column to sum to $1$: $1_{1 \times k} X = 1_{1 \times n}$.
So far, this coloring does not have to respect the edges of the graph, so let's add that condition. The coloring $X$ is a proper $k$-coloring if $XB \le 1_{k \times m}$ (that is, every entry of $XB$ is at most $1$). Then, the chromatic number is the minimum number of rows in $X$ such that this holds.