IJPAM: Volume 101, No. 7 (2015)

CHROMATIC LAYOUT NUMBER OF CERTAIN TREES

Jasintha Quadras$^1$, S. Vasanthika$^2$
$^1$Stella Maris College
Chennai, 600 034, INDIA
$^2$VIT University
Chennai, 600 127, INDIA


Abstract. A linear layout, or simply a layout, of an undirected graph $G = (V, E)$ with $n$ vertices is a bijective function $\phi: V \rightarrow \{1,2,\ldots,n\}$. A k-coloring of a graph $G = (V, E)$ is a mapping $\kappa: V \rightarrow \{c_1, c_2,\ldots, c_k\}$ such that no two adjacent vertices have the same color. A graph with a k-coloring is called a k-colored graph. A colored layout of a k-colored graph $(G, \kappa)$ is a layout $\phi$ of G such that for any $u, x, v \in V$, if $(u, v)\in E$ and $\phi(u) < \phi(x) < \phi(v)$ then $\kappa(u) \neq \kappa(x)$. A k-chromatic layout of $G$ is a k-colored layout of $G$ such that for any t-colored layout of $G$, $t\geq k$. $k$ is called the chromatic layout number of $G$. In this paper we obtain a lower bound for the chromatic layout number for a graph $G$ and prove that the bound is sharp for caterpillars.

Received: March 12, 2015

AMS Subject Classification: 05C05, 05C15

Key Words and Phrases: linear layout, chromatic number, chromatic layout, chromatic layout number, caterpillar

Download paper from here.



DOI: 10.12732/ijpam.v101i7.13 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2015
Volume: 101
Issue: 7
Pages: 713 - 719


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).