Complexity of (p,1)-total labelling

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

zbMATH Keywords

total colouringtotal labellingdistance constrained colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (5)

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

This page was built for publication: Complexity of (p,1)-total labelling