Good edge-labelling of graphs

DOI10.1016/J.DAM.2011.07.021MaRDI QIDQ5916095zbMATH OpenOpenAlexFDO

Authors Júlio Araújo, Nathann Cohen, F. Giroire, Frédéric Havet

Publication date 22 November 2012

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

Full work available at URL https://doi.org/10.1016/j.dam.2011.07.021

zbMATH Keywords

edge-labellingincreasing pathsNP-completeness

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Good edge-labelling of graphs
• On the density of nearly regular graphs with a good edge-labeling
• Edge colouring by total labellings
• On gap-labellings of some families of graphs
• The edge span of distance two labellings of graphs

Cites work

• Extremal graphs having no matching cuts
• scientific article; zbMATH DE number 3869366 (Why is no real title available?)
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• New asymptotics for bipartite Turán numbers
• The complexity of satisfiability problems
• The complexity of the matching-cut problem for planar graphs and other graph classes

Cited in

(17)

• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• On the density of nearly regular graphs with a good edge-labeling
• scientific article; zbMATH DE number 7378605 (Why is no real title available?)
• scientific article; zbMATH DE number 6605161 (Why is no real title available?)
• Good edge-labelling of graphs
• Matching cut in graphs with large minimum degree
• Finding matching cuts in \(H\)-free graphs
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Finding d-cuts in probe H-free graphs
• On the parameterized complexity of computing good edge-labelings
• Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs
• Matching cuts in graphs of high girth and H-free graphs
• Matching cuts in graphs of high girth and \(H\)-free graphs
• Finding \(d\)-cuts in graphs of bounded diameter, graphs of bounded radius and \(H\)-free graphs
• Matching (multi)cut: algorithms, complexity, and enumeration

This page was built for publication: Good edge-labelling of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5916095)