Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
graph colorings; graph homomorphisms; colored mixed graphs
graph colorings; graph homomorphisms; colored mixed graphs
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.
References:
[1] Alon M., Marshall T.H.: Homomorphisms of edge-colored graphs and Coxeter groups. J. Algebraic Combin. 8 (1998), 5-13. DOI 10.1023/A:1008647514949 | MR 1635549 | Zbl 0911.05034
[2] Borodin O.V.: On acyclic colorings of planar graphs. Discrete Math. 25 (1979), 211-236. DOI 10.1016/0012-365X(79)90077-3 | MR 0534939 | Zbl 0406.05031
[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. DOI 10.1016/S0012-365X(98)00393-8 | MR 1665387
[4] Nešetřil J., Raspaud A.: Colored homomorphisms of colored mixed graphs. J. Combin. Theory Ser. B 80 (2000), 1 147-155. DOI 10.1006/jctb.2000.1977 | MR 1778206
[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.: The chromatic number of oriented graphs. J. Graph Theory 25 (1997), 3 191-205. DOI 10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.0.CO;2-G | MR 1451297 | Zbl 0874.05026
[7] Sopena E.: Oriented graph coloring. Discrete Math. 229 (2001), 359-369. DOI 10.1016/S0012-365X(00)00216-8 | MR 1815613 | Zbl 0971.05039
Search
Partner of
