Algorithmic complexity of proper labeling problems
Publication:391137
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
computational complexity1-2-3-conjecturefictional coloringgap vertex-distinguishing edge coloringsmultiplicative 1-2-3-conjecturemultiplicative vertex-coloring weightingsproper labelingvertex-labeling by maximum
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)
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