| Title:
|
Lower bounds for the colored mixed chromatic number of some classes of graphs (English) |
| Author:
|
Fabila-Monroy, R. |
| Author:
|
Flores, D. |
| Author:
|
Huemer, C. |
| Author:
|
Montejano, A. |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
49 |
| Issue:
|
4 |
| Year:
|
2008 |
| Pages:
|
637-645 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graph colorings |
| Keyword:
|
graph homomorphisms |
| Keyword:
|
colored mixed graphs |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 1212.05076 |
| idMR:
|
MR2493943 |
| . |
| Date available:
|
2009-05-05T17:13:37Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119751 |
| . |
| Reference:
|
[1] Alon M., Marshall T.H.: Homomorphisms of edge-colored graphs and Coxeter groups.J. Algebraic Combin. 8 (1998), 5-13. Zbl 0911.05034, MR 1635549, 10.1023/A:1008647514949 |
| Reference:
|
[2] Borodin O.V.: On acyclic colorings of planar graphs.Discrete Math. 25 (1979), 211-236. Zbl 0406.05031, MR 0534939, 10.1016/0012-365X(79)90077-3 |
| Reference:
|
[3] Borodin O.V., Kostochka A.V., Nešetřil J., Raspaud A., Sopena E.: On the maximum average degree and the oriented chromatic number of a graph.Discrete Math. 206 (1999), 1-3 77-89. MR 1665387, 10.1016/S0012-365X(98)00393-8 |
| Reference:
|
[4] Nešetřil J., Raspaud A.: Colored homomorphisms of colored mixed graphs.J. Combin. Theory Ser. B 80 (2000), 1 147-155. MR 1778206, 10.1006/jctb.2000.1977 |
| Reference:
|
[5] Ochem P.: Negative results on acyclic improper colorings.EuroComb 2005. Berlin, September 5-9, 2005. DMTCS Conference Volume AE (2005), pp.357-362. |
| Reference:
|
[6] Sopena E.: The chromatic number of oriented graphs.J. Graph Theory 25 (1997), 3 191-205. Zbl 0874.05026, MR 1451297, 10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G |
| Reference:
|
[7] Sopena E.: Oriented graph coloring.Discrete Math. 229 (2001), 359-369. Zbl 0971.05039, MR 1815613, 10.1016/S0012-365X(00)00216-8 |
| . |
