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

DOI10.1007/S00373-014-1446-9zbMATH Open1321.05082arXiv1403.1182OpenAlexW3101915495MaRDI QIDQ497328FDOQ497328

Authors: A. Dehghan, Mohammad-Reza Sadeghi, A. Ahadi 

Publication date: 24 September 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• NP completeness of finding the chromatic index of regular graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Graph factors and factorization: 1985--2003: a survey
• The NP-Completeness of Some Edge-Partition Problems
• Complexité de l'arboricité linéaire d'un graphe
• 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 regular number of a graph
• Complexity of approximation of 3-edge-coloring of graphs

Cited In (8)

• On the algorithmic complexity of zero-sum edge-coloring
• 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
• Path partitions of phylogenetic networks
• Equitable scheduling on a single machine
• Colorful edge decomposition of graphs: some polynomial cases
• 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)