The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties

DOI10.1016/J.TCS.2023.113758MaRDI QIDQ2686111zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 24 February 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.tcs.2023.113758

zbMATH Keywords

chromatic numberconnectivityNP-completenessout-branchingspolynomial algorithmspanning trees

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• scientific article; zbMATH DE number 3889547
• Arc-disjoint spanning sub(di)graphs in digraphs
• Spanning trees with many or few colors in edge-colored graphs
• On the complexity of packing rainbow spanning trees

Cites work

• A short proof of the tree-packing theorem
• Arc-disjoint spanning sub(di)graphs in digraphs
• Bipartite spanning sub(di)graphs induced by 2-partitions
• Digraphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• scientific article; zbMATH DE number 50766 (Why is no real title available?)
• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• NP-completeness of some problems of partitioning and covering in graphs
• On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
• On some extremal problems in graph theory
• On the Problem of Decomposing a Graph into n Connected Factors
• On two minimax theorems in graph

Cited in

(1)

• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties

This page was built for publication: The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2686111)