Abstract
A mixed graphG π contains both undirected edges and directed arcs. Ak-coloring ofG π is an assignment to its vertices of integers not exceedingk (also called colors) so that the endvertices of an edge have different colors and the tail of any arc has a smaller color than its head. The chromatic number γπ(G) of a mixed graph is the smallestk such thatG π admits ak-coloring. To the best of our knowledge it is studied here for the first time. We present bounds of γ(G), discuss algorithms to find this quantity for trees and general graphs, and report computational experience.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Atkinson MD, Sack J-R, Santoro N, Strothotte T (1986) Min-max heaps and generalized priority queues. Communications of the Association for Computing Machinery 29:996–1000
Balas E (1969) Machine sequencing via disjunctive graphs: An implicit enumeration approach. Operations Research 17:941–957
Gallai T (1968) On directed paths and circuits. In: Erdös P, Katona G (Eds.) Theory of graphs — proceedings of the colloquium held at Tihany, Hungary. Academic Press
Matula DW, Marble G, Isaacson JD (1972) Graph coloring algorithms. In: Read RC (Ed.) Graph Theory and Computing. Academic Press
Roy B (1966) Prise en compte des contraintes disjonctives dans les méthodes de chemin critique. RAIRO 38:69–84
Roy B (1967) Nombre chromatique et plus longs chemins d'un graphe. Revue Française d'Informatique et de Recherche Opérationnelle 1:129–132
Tarjan RE (1983) Data structures and network algorithms. SIAM
Vitaver LM (1962) Determination of minimal colorings for vertices of a graph by means of Boolean powers of the adjacency martix. Soviet Mathematics — Doklady 3, no 6:1687–1688
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hansen, P., Kuplinsky, J. & de Werra, D. Mixed graph colorings. Mathematical Methods of Operations Research 45, 145–160 (1997). https://doi.org/10.1007/BF01194253
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01194253