Lower bounds for the colored mixed chromatic number of some classes of graphs

Ruy Fabila Monroy; D. Flores; Clemens Huemer; A. Montejano

Commentationes Mathematicae Universitatis Carolinae (2008)

  • Volume: 49, Issue: 4, page 637-645
  • ISSN: 0010-2628

Abstract

top
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šetřil and Raspaud in Colored homomorphisms of colored mixed graphs, J. Combin. Theory Ser. B 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.

How to cite

top

Fabila Monroy, Ruy, et al. "Lower bounds for the colored mixed chromatic number of some classes of graphs." Commentationes Mathematicae Universitatis Carolinae 49.4 (2008): 637-645. <http://eudml.org/doc/250489>.

@article{FabilaMonroy2008,
abstract = {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šetřil and Raspaud in Colored homomorphisms of colored mixed graphs, J. Combin. Theory Ser. B 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.},
author = {Fabila Monroy, Ruy, Flores, D., Huemer, Clemens, Montejano, A.},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph colorings; graph homomorphisms; colored mixed graphs; graph colorings; graph homomorphisms; colored mixed graphs},
language = {eng},
number = {4},
pages = {637-645},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Lower bounds for the colored mixed chromatic number of some classes of graphs},
url = {http://eudml.org/doc/250489},
volume = {49},
year = {2008},
}

TY - JOUR
AU - Fabila Monroy, Ruy
AU - Flores, D.
AU - Huemer, Clemens
AU - Montejano, A.
TI - Lower bounds for the colored mixed chromatic number of some classes of graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2008
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 49
IS - 4
SP - 637
EP - 645
AB - 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šetřil and Raspaud in Colored homomorphisms of colored mixed graphs, J. Combin. Theory Ser. B 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.
LA - eng
KW - graph colorings; graph homomorphisms; colored mixed graphs; graph colorings; graph homomorphisms; colored mixed graphs
UR - http://eudml.org/doc/250489
ER -

References

top
  1. Alon M., Marshall T.H., 10.1023/A:1008647514949, J. Algebraic Combin. 8 (1998), 5-13. (1998) Zbl0911.05034MR1635549DOI10.1023/A:1008647514949
  2. Borodin O.V., 10.1016/0012-365X(79)90077-3, Discrete Math. 25 (1979), 211-236. (1979) Zbl0406.05031MR0534939DOI10.1016/0012-365X(79)90077-3
  3. Borodin O.V., Kostochka A.V., Nešetřil J., Raspaud A., Sopena E., 10.1016/S0012-365X(98)00393-8, Discrete Math. 206 (1999), 1-3 77-89. (1999) MR1665387DOI10.1016/S0012-365X(98)00393-8
  4. Nešetřil J., Raspaud A., 10.1006/jctb.2000.1977, J. Combin. Theory Ser. B 80 (2000), 1 147-155. (2000) MR1778206DOI10.1006/jctb.2000.1977
  5. Ochem P., Negative results on acyclic improper colorings, EuroComb 2005. Berlin, September 5-9, 2005. DMTCS Conference Volume AE (2005), pp.357-362. 
  6. Sopena E., 10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G, J. Graph Theory 25 (1997), 3 191-205. (1997) Zbl0874.05026MR1451297DOI10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G
  7. Sopena E., 10.1016/S0012-365X(00)00216-8, Discrete Math. 229 (2001), 359-369. (2001) Zbl0971.05039MR1815613DOI10.1016/S0012-365X(00)00216-8

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.