Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
Linear-time algorithm for the edge-colorability of a graph with prescribed vertex types
Authors: Zs. Tuza, V. Voloshin
– 0.13 Mb
Abstract
We consider the coloring of edges in a graph in which there are vertices of three types. In a feasible edge coloring, each vertex of the first type is incident with at least two edges of the same color, and each vertex of the second type with at least two edges of different colors; while no constraints are required for the vertices of the third type. We present a characterization of colorable graphs, and a linear-time algorithm to decide whether a given graph with prescribed vertex types admits a feasible edge coloring.Z.Tuza, V.Voloshin,
Zsolt Tuza
Computer and Automation Institute
Hungarian Academy of Sciences
H-1111 Budapest, Kende u. 13-17, Hungary
Vitaly Voloshin
Institute of Mathematics and Computer Science
Moldovan Academy of Sciences
MD-2028 Chisinau, str. Academiei 5, Moldova
Zsolt Tuza
Computer and Automation Institute
Hungarian Academy of Sciences
H-1111 Budapest, Kende u. 13-17, Hungary
Vitaly Voloshin
Institute of Mathematics and Computer Science
Moldovan Academy of Sciences
MD-2028 Chisinau, str. Academiei 5, Moldova
Fulltext
– 0.13 Mb
Contents
- The splitting method and Poincare's theorem: (II) - matrix, polynomial and language
- On stability of Nash equilibrium situations and Pareto optimal situations in finite games
- Linear-time algorithm for the edge-colorability of a graph with prescribed vertex types
- Supermodular Programming on Lattices
- Fast software-oriented hash function based on data-dependent lookup operations
- About some problems related to collective expertise
- Yurii Nikolaevich Pechersky (a tribute in his memory)
- The jubilee of IM&CS
