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
Voir la notice de l'article provenant de 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.
@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},
publisher = {mathdoc},
volume = {49},
number = {4},
year = {2008},
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 PB - mathdoc 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 %I mathdoc %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/