Complexity framework for forbidden subgraphs I: The framework

M Johnson, B Martin, JJ Oostveen, S Pandey… - Algorithmica, 2025 - Springer
For a set of graphs\({\mathcal {H}}\), a graph G is\({\mathcal {H}}\)-subgraph-free if G does
not contain any graph from\({{{\mathcal {H}}}}\) as a subgraph. We propose general and easy …

Injective edge coloring of graphs with maximum degree 5

J Zhu - Discrete Applied Mathematics, 2023 - Elsevier
A k-injective-edge coloring of a graph G is an edge coloring c: E (G)→{1, 2,…, k} such that c
(e 1)≠ c (e 3) for any three consecutive edges e 1, e 2, e 3 of a path or a 3-cycle. The …

Injective edge coloring for graphs with small edge weight

J Lu, H Liu, X Hu - Graphs and Combinatorics, 2022 - Springer
An injective k-edge coloring of a graph G=(V (G), E (G)) is ak-edge coloring φ such that if e 1
and e 2 are at distance exactly 2 or in the same triangle, then φ (e 1)≠ φ (e 2). The injective …

Injective edge coloring of sparse graphs with maximum degree 5

J Zhu, Y Bu, H Zhu - Journal of Combinatorial Optimization, 2023 - Springer
A k-injective-edge coloring of a graph G is a mapping c: E (G)→{1, 2,⋯, k} such that c (e 1)≠
c (e 3) for any three consecutive edges e 1, e 2, e 3 of a path or a 3-cycle. χ i′(G)= min {k| G …

Edge open packing: complexity, algorithmic aspects, and bounds

B Brešar, B Samadi - arXiv preprint arXiv:2403.00750, 2024 - arxiv.org
Given a graph $ G $, two edges $ e_ {1}, e_ {2}\in E (G) $ are said to have a common edge $
e $ if $ e $ joins an endvertex of $ e_ {1} $ to an endvertex of $ e_ {2} $. A subset …

Complexity and algorithms for injective edge coloring of graphs

BS Panda - Theoretical Computer Science, 2023 - Elsevier
An injective k-edge-coloring of a graph G=(V, E) is an assignment ω: E→{1, 2,…, k} of colors
to the edges of G such that any two edges e and f receive distinct colors if there exists an …

Injective chromatic index of sparse graphs

Y Bu, P Wang, H Zhu, J Zhu - Discrete Applied Mathematics, 2024 - Elsevier
A k-injective-edge coloring of a graph G is an assignment of colors, ie integers in {1, 2,…, k},
to the edges of G such that e 1 and e 3 receive distinct colors for any three consecutive …

Injective edge chromatic index of generalized Petersen graphs

X Hu, BM Legass - Bulletin of the Malaysian Mathematical Sciences …, 2023 - Springer
An injective k-edge coloring of a graph G=(V (G), E (G)) is ak-edge coloring φ of G such that
φ (e 1)≠ φ (e 3) for any three consecutive edges e 1, e 2 and e 3 of a path or a 3-cycle. The …

Injective edge-coloring of claw-free subcubic graphs

Q Cui, Z Han - Journal of Combinatorial Optimization, 2024 - Springer
An injective edge-coloring of a graph G is an edge-coloring of G such that any two edges
that are at distance 2 or in a common triangle receive distinct colors. The injective chromatic …

On injective chromatic index of sparse graphs with maximum degree 5

J Lu, ZM Hong, ZJ Xia - Journal of Combinatorial Optimization, 2024 - Springer
Abstract A k-edge coloring\(\varphi\) of a graph G is injective if\(\varphi (e_1)\ne\varphi
(e_3)\) for any three consecutive edges\(e_1, e_2\) and\(e_3\) of a path or a triangle. The …