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

DOI10.1007/s00373-014-1446-9zbMath1321.05082arXiv1403.1182MaRDI 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 complexity; edge-partition problems; not-all-equal 3-sat problem; regular number

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

05C20: Directed graphs (digraphs), tournaments

Related Items

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 the proper arc labeling of directed graphs, On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}, Colorful edge decomposition of graphs: some polynomial cases, On the algorithmic complexity of zero-sum edge-coloring

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