Locally irregular edge-coloring of subcubic graphs (Q6064843): Difference between revisions

A graph is locally irregular if no two adjacent vertices have the same degree. A locally irregular edge coloring (LIEC) of a graph is an (improper) edge coloring such that every color class induces a locally irregular subgraph. Not every graph has a LIEC; \(K_2\) is an obvious counterexample. This notion of edge coloring was introduced by \textit{O. Baudon} et al. [Eur. J. Comb. 49, 90--104 (2015; Zbl 1315.05105)], who conjectured that every graph that admits a LIEC has such a coloring with three colors. This was disproved by \textit{J. Sedlar} and \textit{R. Škrekovski} [Mathematics 9, No. 24, Paper No. 3209, 10 p. (2021; \url{doi:10.3390/math9243209})], who instead suggested that this holds for every connected graph with a LIEC except for a small cactus graph with maximum degree \(4\) which requires four colors. This latter conjecture has been verified for e.g. regular graphs with degree at least \(10^7\) [\textit{O. Baudon} et al., Eur. J. Comb. 49, 90--104 (2015; Zbl 1315.05105)], graphs with minimum degree at least \(10^9\) [\textit{J. Przybyło}, Electron. J. Comb. 23, No. 2, Research Paper P2.31, 13 p. (2016; Zbl 1338.05237)], and trees [\textit{O. Baudon} et al., J. Discrete Algorithms 30, 113--127 (2015; Zbl 1320.05036)]. In this paper, the authors consider the conjecture of Baudon et al. [Zbl 1315.05105, loc. cit.] for subcubic graphs. It was proved in [\textit{B. Lužar} et al., J. Comb. Optim. 36, No. 4, 1425--1438 (2018; Zbl 1410.05072)] that if a subcubic graph has a LIEC, then it has such a coloring with four colors. The authors improve on this result by settling the conjecture in the affirmative for subcubic claw-free graphs, cycle permutation graphs, and generalized Petersen graphs. Moreover, motivated by the fact that cubic bipartite graphs admit a LIEC with \(2\) colors [Baudon et al., loc. cit (2015)], they present some remarks and open problems on the existence of \(2\)-LIECs of cubic and bipartite graphs.