On the complexity of \(k\)-rainbow cycle colouring problems

DOI10.1016/j.dam.2018.09.036zbMath1414.05121arXiv1706.00546OpenAlexW2963122920MaRDI QIDQ2422742

Yan Zhao, Shasha Li, Yongtang Shi, Jian-hua Tu

Publication date: 20 June 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.00546

zbMATH Keywords

NP-completenesspolynomial timerainbow cycle\(k\)-rainbow cycle colouring\(k\)-rainbow cycle index

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Some results on the 3-total-rainbow index ⋮ Relations of three classes of disconnected coloring ⋮ Extremal stretch of proper-walk coloring of graphs

Cites Work

• Unnamed Item
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Hardness and algorithms for rainbow connection
• The complexity of determining the rainbow vertex-connection of a graph
• Cycles through specified vertices
• Further hardness results on rainbow and strong rainbow connectivity
• On rainbow connection
• Cycles through specified vertices of a graph
• Total rainbow connection of digraphs
• Rainbow vertex connection of digraphs
• Rainbow connections of graphs: a survey
• Note on the hardness of rainbow connections for planar and line graphs
• Rainbow trees in graphs and generalized connectivity
• 4‐chrome Graphen und vollständige 4‐Graphen
• Rainbow connection in graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

This page was built for publication: On the complexity of \(k\)-rainbow cycle colouring problems