The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree

DOI10.1016/j.disc.2008.09.028zbMath1205.05225OpenAlexW2093844568MaRDI QIDQ1025950

Adrian Kosowski, Robert Janczewski, Michał Małafiejski

Publication date: 23 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.09.028

zbMATH Keywords

planar graphsbipartite graphs\(L(p, q)\)-labelinggraphs of small degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An \(O(n\log n)\) algorithm for finding edge span of cacti, The complexity of \(L(p, q)\)-edge-labelling, Fast exact algorithm for \(L(2,1)\)-labeling of graphs, Locally injective \(k\)-colourings of planar graphs, Determining the \(L(2,1)\)-span in polynomial space, Fast Exact Algorithm for L(2,1)-Labeling of Graphs, The complexity of \(L(p, q)\)-edge-labelling, On the Complexity of Planar Covering of Small Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• A survey on labeling graphs with a condition at distance two
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Approximations for  -Colorings of Graphs
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
• The $L(2,1)$-Labeling Problem on Graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• Hard tiling problems with simple tiles