On the complexity of deciding whether the regular number is at most two

DOI10.1007/s00373-014-1446-9zbMath1321.05082arXiv1403.1182OpenAlexW3101915495MaRDI QIDQ497328

Mohammad-Reza Sadeghi, Ali Dehghan, Arash Ahadi

Publication date: 24 September 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityedge-partition problemsnot-all-equal 3-sat problemregular number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (7)

On the algorithmic complexity of zero-sum edge-coloring ⋮ Colorful edge decomposition of graphs: some polynomial cases ⋮ Equitable scheduling on a single machine ⋮ Algorithmic complexity of weakly semiregular partitioning and the representation number ⋮ On the in-out-proper orientations of graphs ⋮ On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat} ⋮ On the proper arc labeling of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Graph factors and factorization: 1985--2003: a survey
• Complexity of approximation of 3-edge-coloring of graphs
• Polynomial cases of graph decomposition: A complete solution of Holyer's problem
• On the complexity of some edge-partition problems for graphs
• Regular number of a graph
• The NP-Completeness of Some Edge-Partition Problems
• Complexité de l'arboricité linéaire d'un graphe
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• The regular number of a graph
• NP completeness of finding the chromatic index of regular graphs

This page was built for publication: On the complexity of deciding whether the regular number is at most two