  Motivated by the definition of linear coloring on simplicial complexes,
recently introduced in the context of algebraic topology \cite{Civan}, and the
framework through which it was studied, we introduce the linear coloring on
graphs. We provide an upper bound for the chromatic number $\chi(G)$, for any
graph $G$, and show that $G$ can be linearly colored in polynomial time by
proposing a simple linear coloring algorithm. Based on these results, we define
a new class of perfect graphs, which we call co-linear graphs, and study their
complement graphs, namely linear graphs. The linear coloring of a graph $G$ is
a vertex coloring such that two vertices can be assigned the same color, if
their corresponding clique sets are associated by the set inclusion relation (a
clique set of a vertex $u$ is the set of all maximal cliques containing $u$);
the linear chromatic number $\mathcal{\lambda}(G)$ of $G$ is the least integer
$k$ for which $G$ admits a linear coloring with $k$ colors. We show that linear
graphs are those graphs $G$ for which the linear chromatic number achieves its
theoretical lower bound in every induced subgraph of $G$. We prove inclusion
relations between these two classes of graphs and other subclasses of chordal
and co-chordal graphs, and also study the structure of the forbidden induced
subgraphs of the class of linear graphs.
