Complexity and algorithms for injective edge-coloring in graphs

DOI10.1016/j.ipl.2021.106121OpenAlexW3156849144WikidataQ114167103 ScholiaQ114167103MaRDI QIDQ2032162

Florent Foucaud, Dimitri Lajou, Hervé Hocquard

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

planar graphstreewidthgraph algorithmssubcubic graphsinjective edge-coloring

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (8)

Injective edge coloring of some sparse graphs ⋮ Injective edge coloring for graphs with small edge weight ⋮ Injective edge coloring of power graphs and necklaces ⋮ Complexity and algorithms for injective edge coloring of graphs ⋮ Injective chromatic index of sparse graphs ⋮ Injective edge coloring of graphs with maximum degree 5 ⋮ Injective edge chromatic index of generalized Petersen graphs ⋮ Injective edge coloring of sparse graphs with maximum degree 5

Cites Work

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

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