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

DOI10.1007/S00373-014-1446-9MaRDI QIDQ497328zbMATH OpenOpenAlexFDO

Authors A. Dehghan, Mohammad-Reza Sadeghi, A. 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

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

Abstract: The regular number of a graph G denoted by reg(G) is the minimum number of subsets into which the edge set of G can be partitioned so that the subgraph induced by each subset is regular. In this work we answer to the problem posed as an open problem in A. Ganesan et al. (2012) [3] about the complexity of determining the regular number of graphs. We show that computation of the regular number for connected bipartite graphs is NP-hard. Furthermore, we show that, determining whether reg(G) = 2 for a given connected 3-colorable graph G is NP-complete. Also, we prove that a new variant of the Monotone Not-All-Equal 3-Sat problem is NP-complete.

Recommendations

• The regular number of a graph
• The complexity of regular subgraph recognition
• A note on the complexity of finding regular subgraphs
• Total colouring regular bipartite graphs is NP-hard
• Complexity of finding maximum regular induced subgraphs with prescribed degree

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Complexity of approximation of 3-edge-coloring of graphs
• Complexité de l'arboricité linéaire d'un graphe
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Graph factors and factorization: 1985--2003: a survey
• NP completeness of finding the chromatic index of regular graphs
• On the complexity of some edge-partition problems for graphs
• Polynomial cases of graph decomposition: A complete solution of Holyer's problem
• Regular number of a graph
• The NP-Completeness of Some Edge-Partition Problems
• The regular number of a graph

Cited in

(8)

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

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

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