Computer Science – Discrete Mathematics
Scientific paper
2008-07-26
Computer Science
Discrete Mathematics
21 pages, 7 figures
Scientific paper
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.
Ioannidou Kyriaki
Nikolopoulos Stavros D.
No associations
LandOfFree
Linear Coloring and Linear Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Linear Coloring and Linear Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Coloring and Linear Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-314634