Algorithmic complexity of weakly semiregular partitioning and the representation number

DOI10.1016/J.TCS.2017.01.028zbMath1369.68224arXiv1701.05934OpenAlexW2963515165MaRDI QIDQ528476

Mohsen Mollahajiaghaei, Arash Ahadi, Ali Dehghan

Publication date: 12 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

locally irregular graphrepresentation numberedge-partition problemssemiregular numberweakly semiregular number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• Decomposing graphs into a constant number of locally irregular subgraphs
• Algorithmic complexity of proper labeling problems
• Representation numbers of complete multipartite graphs
• Computation of lucky number of planar graphs is NP-hard
• On the unitary Cayley graphs of matrix algebras
• On the complexity of deciding whether the regular number is at most two
• On a directed variation of the 1-2-3 and 1-2 conjectures
• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
• Graph factors and factorization: 1985--2003: a survey
• Covering planar graphs with forests, one having bounded maximum degree
• Representations of graphs modulo \(n\)
• Covering planar graphs with forests
• On the complexity of determining the irregular chromatic index of a graph
• On decomposing regular graphs into locally irregular subgraphs
• Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs
• Regular number of a graph
• The inapproximability for the (0,1)-additive number
• Representations of graphs and orthogonal latin square graphs
• On the Complexity of General Graph Factor Problems
• On the connectivity of semiregular cages
• Orthogonal latin square graphs
• The NP-Completeness of Some Edge-Partition Problems
• The NP-Completeness of Edge-Coloring
• On the Decomposition of Graphs
• Representations of graphs modulo n
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• The regular number of a graph
• An algorithmic proof of Tutte's f-factor theorem
• Sequence variations of the 1-2-3 Conjecture and irregularity strength

This page was built for publication: Algorithmic complexity of weakly semiregular partitioning and the representation number