Lower bounds for the colored mixed chromatic number of some classes of graphs
Commentationes Mathematicae Universitatis Carolinae, Tome 49 (2008) no. 4, pp. 637-645
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library
A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph $G$ is defined as the smallest order of a colored mixed graph $H$ such that there exists a (color preserving) homomorphism from $G$ to $H$. These notions were introduced by Ne\v{s}et\v{r}il and Raspaud in {\it Colored homomorphisms of colored mixed graphs\/}, J. Combin. Theory Ser. B {\bf 80} (2000), no. 1, 147--155, where the exact chromatic number of colored mixed trees was given. We prove here that this chromatic number is reached by the much simpler family of colored mixed paths. By means of this result we give lower bounds for the chromatic number of colored mixed partial $k$-trees, outerplanar and planar graphs.
A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph $G$ is defined as the smallest order of a colored mixed graph $H$ such that there exists a (color preserving) homomorphism from $G$ to $H$. These notions were introduced by Ne\v{s}et\v{r}il and Raspaud in {\it Colored homomorphisms of colored mixed graphs\/}, J. Combin. Theory Ser. B {\bf 80} (2000), no. 1, 147--155, where the exact chromatic number of colored mixed trees was given. We prove here that this chromatic number is reached by the much simpler family of colored mixed paths. By means of this result we give lower bounds for the chromatic number of colored mixed partial $k$-trees, outerplanar and planar graphs.
@article{CMUC_2008_49_4_a8,
author = {Fabila-Monroy, R. and Flores, D. and Huemer, C. and Montejano, A.},
title = {Lower bounds for the colored mixed chromatic number of some classes of graphs},
journal = {Commentationes Mathematicae Universitatis Carolinae},
pages = {637--645},
year = {2008},
volume = {49},
number = {4},
mrnumber = {2493943},
zbl = {1212.05076},
language = {en},
url = {http://geodesic.mathdoc.fr/item/CMUC_2008_49_4_a8/}
}
TY - JOUR AU - Fabila-Monroy, R. AU - Flores, D. AU - Huemer, C. AU - Montejano, A. TI - Lower bounds for the colored mixed chromatic number of some classes of graphs JO - Commentationes Mathematicae Universitatis Carolinae PY - 2008 SP - 637 EP - 645 VL - 49 IS - 4 UR - http://geodesic.mathdoc.fr/item/CMUC_2008_49_4_a8/ LA - en ID - CMUC_2008_49_4_a8 ER -
%0 Journal Article %A Fabila-Monroy, R. %A Flores, D. %A Huemer, C. %A Montejano, A. %T Lower bounds for the colored mixed chromatic number of some classes of graphs %J Commentationes Mathematicae Universitatis Carolinae %D 2008 %P 637-645 %V 49 %N 4 %U http://geodesic.mathdoc.fr/item/CMUC_2008_49_4_a8/ %G en %F CMUC_2008_49_4_a8
Fabila-Monroy, R.; Flores, D.; Huemer, C.; Montejano, A. Lower bounds for the colored mixed chromatic number of some classes of graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 49 (2008) no. 4, pp. 637-645. http://geodesic.mathdoc.fr/item/CMUC_2008_49_4_a8/