Algorithmic complexity of proper labeling problems

DOI10.1016/j.tcs.2013.05.027zbMath1295.05203arXiv1701.06669OpenAlexW1999771492MaRDI QIDQ391137

Mohammad-Reza Sadeghi, Arash Ahadi, Ali Dehghan

Publication date: 10 January 2014

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

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

zbMATH Keywords

computational complexity1-2-3-conjecturefictional coloringgap vertex-distinguishing edge coloringsmultiplicative 1-2-3-conjecturemultiplicative vertex-coloring weightingsproper labelingvertex-labeling by maximum

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (24)

On the complexity of gap-\([2\)-vertex-labellings of subcubic bipartite graphs] ⋮ Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs ⋮ On strongly planar not-all-equal 3SAT ⋮ On locally irregular decompositions of subcubic graphs ⋮ Colorful edge decomposition of graphs: some polynomial cases ⋮ Additive list coloring of planar graphs with given girth ⋮ Is there any polynomial upper bound for the universal labeling of graphs? ⋮ On gap-labellings of some families of graphs ⋮ Graphs without gap-vertex-labellings: families and bounds ⋮ The weak \((2, 2)\)-labelling problem for graphs with forbidden induced structures ⋮ A notion of vertex equitability for proper labellings ⋮ On inducing degenerate sums through 2-labellings ⋮ Population-based iterated greedy algorithm for the S-labeling problem ⋮ On the role of 3's for the 1-2-3 conjecture ⋮ On the role of 3s for the 1--2--3 conjecture ⋮ Algorithmic complexity of weakly semiregular partitioning and the representation number ⋮ On the complexity of determining the irregular chromatic index of a graph ⋮ Algorithmic expedients for the \(S\)-labeling problem ⋮ A lower bound and several exact results on the \(d\)-lucky number ⋮ On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ On \(\{a, b\}\)-edge-weightings of bipartite graphs with odd \(a, b\) ⋮ Edge weights and vertex colours: minimizing sum count ⋮ On the hardness of determining the irregularity strength of graphs

Cites Work

• Computation of lucky number of planar graphs is NP-hard
• Multiplicative vertex-colouring weightings of graphs
• Gap vertex-distinguishing edge colorings of graphs
• The sigma chromatic number of a graph
• Digraphs are 2-weight choosable
• 1,2 conjecture-the multiplicative version
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Lucky labelings of graphs
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Edge weights and vertex colours
• On the lucky choice number of graphs
• Degree constrained subgraphs
• Vertex colouring edge partitions
• \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
• Weight choosability of graphs
• The NP-Completeness of Edge-Coloring
• The Even Cycle Problem for Directed Graphs
• Vertex-distinguishing proper edge-colorings
• Adjacent Vertex Distinguishing Edge‐Colorings
• Hard tiling problems with simple tiles
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithmic complexity of proper labeling problems