Sufficient conditions for the existence of spanning colored trees in edge-colored graphs
| Autor: | Raquel Águeda, Valentin Borozan, Yannis Manoussakis, Rahul Muthu, Gervais Mendy |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Sufficient conditions
Discrete mathematics Spanning tree Trémaux tree Proper spanning trees ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION Edge (geometry) Theoretical Computer Science Combinatorics Indifference graph Colored Chordal graph Discrete Mathematics and Combinatorics Focus (optics) Edge-colored graphs MathematicsofComputing_DISCRETEMATHEMATICS Mathematics Minimum degree spanning tree |
| Zdroj: | Discrete Mathematics. 312:2694-2699 |
| ISSN: | 0012-365X |
| Popis: | In this paper we study the existence of properly colored spanning trees in edge-colored graphs, under certain assumptions on the graph, both structural and related to the coloring. The general problem of proper spanning trees in edge-colored graphs is not only combinatorially difficult but also computationally hard. Here, we focus on some questions of this important combinatorial problem on sufficient degrees involving connectivity and colored degrees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect