Linear Coloring and Linear Graphs

Simple item page
dc.creatorIoannidou, Kyriaki
dc.creatorNikolopoulos, Stavros D.
dc.date2008-07-26
dc.date.accessioned2026-07-07T09:53:09Z
dc.date.available2026-07-07T09:53:09Z
dc.descriptionMotivated 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 $χ(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λ(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.
dc.description21 pages, 7 figures
dc.identifierhttps://arxiv.org/abs/0807.4234
dc.identifierhttp://arxiv.org/abs/0807.4234
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/165849
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectG.2.2; F.2.2
dc.titleLinear Coloring and Linear Graphs
dc.typetext

Files

Collections

arXiv