Complexity of (p,1)-total labelling
From MaRDI portal
Publication:967327
DOI10.1016/j.dam.2009.03.021zbMath1209.05212OpenAlexW2161923886MaRDI QIDQ967327
Frédéric Havet, Steéphan Thomassé
Publication date: 28 April 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.03.021
Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items
\((2,1)\)-total labeling of a class of subcubic graphs, Computational complexity of distance edge labeling, \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\), Facial \([r,s,t\)-colorings of plane graphs], The \((p,q)\)-total labeling problem for trees
Cites Work
- Unnamed Item
- Determining the total colouring number is NP-hard
- Total colouring regular bipartite graphs is NP-hard
- \((p,1)\)-total labelling of graphs
- A survey on labeling graphs with a condition at distance two
- Labelling Graphs with a Condition at Distance 2
- The $L(2,1)$-Labeling Problem on Graphs
- The complexity of satisfiability problems
- Fixed-parameter complexity of \(\lambda\)-labelings