Complexity and algorithms for injective edge-coloring in graphs

DOI10.1016/J.IPL.2021.106121MaRDI QIDQ2032162zbMATH OpenOpenAlexWikidataFDO

Authors Florent Foucaud, Hervé Hocquard, Dimitri Lajou

Publication date 16 June 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.08003

zbMATH Keywords

graph algorithmsinjective edge-coloringplanar graphssubcubic graphstreewidth

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Injective edge-coloring of subcubic graphs
• Injective edge coloring of planar graphs
• List injective edge-coloring of subcubic graphs
• Note on injective edge-coloring of graphs
• On the complexity of injective colorings and its generalizations

Cites work

• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• Induced and weak induced arboricities
• Injective edge coloring of graphs
• Injective edge coloring of sparse graphs
• List star edge-coloring of \(k\)-degenerate graphs and \(K_4\)-minor free graphs
• New linear-time algorithms for edge-coloring planar graphs
• Note on the perfect EIC-graphs
• NP completeness of finding the chromatic index of regular graphs
• On the injective chromatic number of graphs
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Problems and results in combinatorial analysis and graph theory
• Some simplified NP-complete graph problems
• Strong edge-colouring and induced matchings
• The NP-Completeness of Edge-Coloring
• Treewidth. Computations and approximations

Cited in

(25)

• Injective edge-coloring of graphs with given maximum degree
• List injective edge-coloring of subcubic graphs
• Note on injective edge-coloring of graphs
• Injective edge chromatic index of generalized Petersen graphs
• Injective edge coloring of sparse graphs with maximum degree 5
• Injective coloring of some subclasses of bipartite graphs and chordal graphs
• Injective edge coloring for graphs with small edge weight
• On the complexity of injective colorings and its generalizations
• Locally injective k-colourings of planar graphs
• Injective edge coloring of some sparse graphs
• Injective edge coloring of power graphs and necklaces
• Injective edge-coloring of subcubic graphs
• Complexity and algorithms for injective edge coloring of graphs
• Injective chromatic index of sparse graphs
• Injective edge coloring of graphs with maximum degree 5
• Complexity and algorithms for injective edge-coloring in graphs
• Injective edge chromatic index of generalized Petersen graph \(P(ck,k)\)
• Injective edge coloring of some standard graph products
• Injective-edge-coloring of planar graphs with girth restriction
• Injective edge-coloring of claw-free subcubic graphs
• Edge open packing: complexity, algorithmic aspects, and bounds
• Injective coloring of subclasses of chordal graphs
• Injective edge coloring of sparse graphs
• Complexity framework for forbidden subgraphs. I: The framework
• On injective chromatic index of sparse graphs with maximum degree 5

This page was built for publication: Complexity and algorithms for injective edge-coloring in graphs

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