Algorithmic complexity of proper labeling problems

DOI10.1016/J.TCS.2013.05.027MaRDI QIDQ391137zbMATHOpenAlexFDO

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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A proper labeling of a graph is an assignment of integers to some elements of a graph, which may be the vertices, the edges, or both of them, such that we obtain a proper vertex coloring via the labeling subject to some conditions. The problem of proper labeling offers many variants and received a great interest during recent years. We consider the algorithmic complexity of some variants of the proper labeling problems, we present some polynomial time algorithms and $mathbfNP$-completeness results for them.

Recommendations

• Graph labelings and complexity problems: a review
• On the proper arc labeling of directed graphs
• The \(S\)-\textsc{labeling} problem: an algorithmic tour
• On improved exact algorithms for \(L(2,1)\)-labeling of graphs
• Fixed-parameter complexity of \(\lambda\)-labelings

Cites work

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

Cited in

(33)

• Population-based iterated greedy algorithm for the S-labeling problem
• Graph labelings and complexity problems: a review
• A notion of vertex equitability for proper labellings
• On locally irregular decompositions of subcubic graphs
• On \(\{a, b\}\)-edge-weightings of bipartite graphs with odd \(a, b\)
• On the proper arc labeling of directed graphs
• scientific article; zbMATH DE number 7364985 (Why is no real title available?)
• Colorful edge decomposition of graphs: some polynomial cases
• Algorithms for the multiple label placement problem
• On the hardness of optimal vertex relabeling and restricted vertex relabeling
• Algorithmic expedients for the \(S\)-labeling problem
• On the complexity of determining the irregular chromatic index of a graph
• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs
• On the role of 3's for the 1-2-3 conjecture
• On the hardness of determining the irregularity strength of graphs
• On the \(S\)-\textsc{Labeling} problem
• On the role of 3s for the 1-2-3 conjecture
• scientific article; zbMATH DE number 1759551 (Why is no real title available?)
• Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs
• Graphs without gap-vertex-labellings: families and bounds
• Additive list coloring of planar graphs with given girth
• Is there any polynomial upper bound for the universal labeling of graphs?
• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• On the complexity of gap-\([2]\)-vertex-labellings of subcubic bipartite graphs
• The computational complexity of cordial and equitable labelling
• On strongly planar not-all-equal 3SAT
• Algorithmic complexity of weakly semiregular partitioning and the representation number
• On inducing degenerate sums through 2-labellings
• Edge weights and vertex colours: minimizing sum count
• The weak \((2, 2)\)-labelling problem for graphs with forbidden induced structures
• On gap-labellings of some families of graphs
• A lower bound and several exact results on the \(d\)-lucky number
• Algorithms and complexity for a class of combinatorial optimization problems with labelling

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

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