Papers › A note on X̅-coloring and Â-coloring 4-regular graphs
A note on X̅-coloring and Â-coloring 4-regular graphs
Jorik Jooken
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 K_(1,4). Let  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 Â-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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections