Algorithmic complexity of proper labeling problems

DOI10.1016/j.tcs.2013.05.027zbMath1295.05203arXiv1701.06669MaRDI 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 complexity; 1-2-3-conjecture; fictional coloring; gap vertex-distinguishing edge colorings; multiplicative 1-2-3-conjecture; multiplicative vertex-coloring weightings; proper labeling; vertex-labeling by maximum

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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