## Abstract

As usual λ(G) denotes the edge-connectivity of the graph G. It was shown in [2] that every graph G contains a spanning (λ(G)+1)-partite subgraph H such that λ(H)=λ(G) and one can find such a spanning subgraph in polynomial time. We determine the complexity of deciding, for given positive integers r,k whether a graph contains a spanning r-colourable subgraph which is k-edge-connected. We show that the problem is polynomially solvable when r>k and NP-complete otherwise. In fact, combined with the result from [2] above, this means that the problem is polynomially solvable precisely when r is such that every k-edge-connected graph has a spanning r-colourable subgraph which is k-edge-connected. One can show that all graphs whose edge set decomposes into k edge-disjoint spanning trees are 2k-colourable. We consider the problem of deciding whether a given graph G has a collection of k edge-disjoint spanning trees whose union forms an r-colourable spanning subgraph H of G. We show that this problem is polynomially solvable when r≥2k and NP-complete for all other values of r. We also determine the complexity of the analogous problem of deciding whether a digraph D has a collection of k arc-disjoint out-branchings such that the spanning subdigraph formed by the union of the arcs in the branchings is r-colourable.

Original language | English |
---|---|

Article number | 113758 |

Journal | Theoretical Computer Science |

Volume | 949 |

Number of pages | 15 |

ISSN | 0304-3975 |

DOIs | |

Publication status | Published - 9. Mar 2023 |

## Keywords

- Chromatic number
- Connectivity
- NP-completeness
- Out-branchings
- Polynomial algorithm
- Spanning trees