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
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
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
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