Complexity and algorithms for injective edge-coloring in graphs

DOI10.1016/J.IPL.2021.106121MaRDI QIDQ6365437arXivWikidataFDO

Authors Florent Foucaud, Hervé Hocquard, Dimitri Lajou

Publication date 16 April 2021

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)

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.

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)