Complexity and algorithms for injective edge-coloring in graphs

DOI10.1016/J.IPL.2021.106121arXiv2104.08003WikidataQ114167103 ScholiaQ114167103MaRDI QIDQ6365437FDOQ6365437

Hervé Hocquard, Dimitri Lajou, Florent Foucaud

Publication date: 16 April 2021

Abstract: An injective $k$-edge-coloring of a graph $G$ is an assignment of colors, i.e. integers in $1,ldots,k$, to the edges of $G$ such that any two edges each incident with one distinct endpoint of a third edge, receive distinct colors. The problem of determining whether such a $k$-coloring exists is called k-INJECTIVE EDGE-COLORING. We show that 3-INJECTIVE EDGE-COLORING is NP-complete, even for triangle-free cubic graphs, planar subcubic graphs of arbitrarily large girth, and planar bipartite subcubic graphs of girth~6. 4-INJECTIVE EDGE-COLORING remains NP-complete for cubic graphs. For any $kgeq45$, we show that k-INJECTIVE EDGE-COLORING remains NP-complete even for graphs of maximum degree at most $5sqrt3k$. In contrast with these negative results, we show that InjPbName{k} is linear-time solvable on graphs of bounded treewidth. Moreover, we show that all planar bipartite subcubic graphs of girth at least~16 are injectively $3$-edge-colorable. In addition, any graph of maximum degree at most $sqrtk/2$ is injectively $k$-edge-colorable.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

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 Q6365437)