On the complexity of deciding whether the regular number is at most two
From MaRDI portal
Publication:497328
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
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