2024/01/10 by Jorik Jooken, Jooken, Jorik
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2401.05510
openalex publication_date 2024/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let ∂H(u) be the set of edges incident with a vertex u in the graph H. We say that a graph G is H-colorable if there exist total functions f : E(G) → E(H) and g : V(G) → V(H) such that f is a proper edge-coloring of G and for each vertex u ∈ V(G) we have f(∂G(u))=∂H(g(u)). Let X be the graph obtained by adding three parallel edges between two degree one vertices of the graph K1,4. Let A be the graph obtained by adding two pendant edges to two different vertices of a triangle and then adding two edges between the degree two vertex and the two adjacent degree three vertices. Malnegro and Ozeki [Discrete Math. 347(3):113844 (2024)] asked whether every 4-regular graph with an even number of vertices and an even cycle decomposition of size 3 admits an X-coloring or an A-coloring and whether every 2-connected planar 4-regular graph with an even number of vertices admits such a coloring. Additionally, they conjectured that for every 2-edge-connected simple cubic graph G with an even number of edges, the line graph L(G) is X-colorable. In this short note, we discuss two algorithms for deciding whether a graph G is H-colorable. We give a negative answer to the two questions and disprove the conjecture by finding suitable graphs, as verified by two independent algorithms.