A coloring of edges of a graph G is injective if for any two distinct edges e1 and e2,the coloring of e1 and e2 are distinct if they are at distance 2 in G or in a common 3-cycle.The injective chromatic index of G is ...A coloring of edges of a graph G is injective if for any two distinct edges e1 and e2,the coloring of e1 and e2 are distinct if they are at distance 2 in G or in a common 3-cycle.The injective chromatic index of G is the minimum number of colors needed for an injective edge coloring of G.It was conjectured that the injective chromatic index of any subcubic graph is at most 6.In this paper,we partially confirm this conjecture by showing that the injective chromatic index of any claw-free subcubic graph is less than or equal to 6.The bound 6 is tight and our proof implies a linear-time algorithm for finding an injective edge coloring using at most 6 colors for such graphs.展开更多
基金Supported by the National Natural Science Foundation of China(Grant No.11771080).
文摘A coloring of edges of a graph G is injective if for any two distinct edges e1 and e2,the coloring of e1 and e2 are distinct if they are at distance 2 in G or in a common 3-cycle.The injective chromatic index of G is the minimum number of colors needed for an injective edge coloring of G.It was conjectured that the injective chromatic index of any subcubic graph is at most 6.In this paper,we partially confirm this conjecture by showing that the injective chromatic index of any claw-free subcubic graph is less than or equal to 6.The bound 6 is tight and our proof implies a linear-time algorithm for finding an injective edge coloring using at most 6 colors for such graphs.
