Some New Results on Sylvester Colorings of Cubic Graphs

Jul 16, 2026

The paper investigates Sylvester (H-)colorings between cubic multi-graphs, using edge-to-edge mappings that match incident edge sets at vertices. It studies the Petersen coloring conjecture, which asserts P10 ≺ G for every bridgeless cubic graph G, where P10 is the Petersen graph. It defines two key target graphs, S10 and S12, derived from a smallest cubic multi-graph without perfect matchings. The results guarantee edge mappings E(G)→E(S12) and E(G)→E(S10) with large certified sizes of satisfied vertices for cubic multi-graphs.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

Abstract

Introduction and Notations

Graph basics and definitions

Petersen coloring conjecture and related conjectures

Sylvester coloring framework and transitivity

arXiv :2607 .06396v1 [math .CO] 7 Jul 2026 Some new results on Sylvester colorings of cubic graphs Luca Ferrarinia , Vahan Mkrtchyanb,∗ a Université Sorbonne Paris Nord, LIPN, Villetaneuse, 93430, France b Department of Mathematical Sciences Purdue University Fort Wayne Fort Wayne, IN, USA-46805 Abstract If G and H are two cubic multi-graphs, then an H-coloring of G is a mapping f : E (G) → E (H), such that for every v ∈ V (G) there is a vertex x ∈ V (H), such that f(∂G (v)) = ∂H (x) . If G admits an H-coloring then it is common to write H ≺ G. The Petersen coloring conjecture predicts that for any bridgeless cubic graph G one has P10 ≺ G. Here P10 is the Petersen graph. Let f : E (G) → E (H) be any mapping. Define: V (f) = {v ∈ V (G) : ∃x ∈ V (H), f (∂G (v)) = ∂H (x)} . Let S10 be the smallest cubic multi-graph that has no perfect matching. It has ten vertices. Define S12 as the cubic graph that is obtained from S10 , by replacing its unique vertex z adjacent to three bridges with a triangle. In this paper we show that (1) for every cubic multi-graph G with a perfect matching, there is a mapping f : E (G) → E (S12 ) , such that |V(f)| ≥ ~~4~~5 · |V(G)|, and (2) for every cubic multi-graph G, there is a mapping f : E (G) → E (S10 ) , such that |V(f)| ≥ ~~5~~6 · |V(G)| . Our second result improves the ~~4~~5-bound by Hakobyan and the second author from 2018 . Keywords: Cubic Graph, Petersen Coloring Conjecture, Sylvester Coloring, Sylvester Coloring Conjecture 1. Introduction and Notations In this paper, we consider finite, undirected graphs. Graphs do not contain loops, though they may contain parallel edges. In the paper, we consider graphs up to isomorphisms. This implies that the equality G = G′ means that G and G′ are isomorphic. If G is a graph, then let V (G) and E (G) be the sets of vertices and edges of G, respectively. Let ∂G (v) be the set of edges of G that are incident to the vertex v of G. A matching of Gis a subset of E (G) such that no two of them share a vertex. A matching of G is perfect, if it contains |~~ ~~V~~ ~~(G2)~~ ~~| edges. A cut-vertex of a graph is a vertex whose removal increases the number of components of the graph. A block of G is a maximal 2-connected subgraph of G. ∗ Corresponding author Email addresses: [ferrarini@lipn.univ-paris13.fr](ferrarini@lipn.univ-paris13.fr) (Luca Ferrarini), [vmkrtchy@purdue.edu](vmkrtchy@purdue.edu) (Vahan Mkrtchyan) An end-block is a block of G containing at most one cut-vertex of G. A subgraph H of G is even, if every vertex of H has even degree in H. Let G be a cubic graph, and let T be a triangle in G such that each edge of T is of multiplicity one. Such triangles will be called contractable. Let T be a contractable triangle in a cubic graph and e ∈ E (T), moreover, let f be the edge of G that is incident to a vertex of T and is not adjacent to e. Then, e and f will be called opposite edges. We will frequently consider the graph G/T, which is obtained from a cubic graph G by replacing a contractable triangle T with a vertex. We will say that G/T is obtained from G by contracting the triangle T. If G is a cubic graph containing cut-vertices, then any end-block B of G is adjacent to a unique bridge e. We will refer to e as a bridge corresponding to B . Furthermore, if e = (a, b) and a ∈ V (B) , b V (B), then b is called the root of B . We call e a trivial bridge if e is joined to a non-contractable triangle, otherwise it is non-trivial. An alternative view of trivial bridges is the following. Let e be a bridge in a connected cubic graph G. Let G 1 and G2 be the two components of G − e. Then e is a trivial bridge, if at least one of G 1 or G2 has three vertices. For a positive integer t, a t-factor of G is a spanning t-regular subgraph of G. Notice that the set of edges of a 1-factor of G forms a perfect matching of G. Moreover, if G is cubic and M is a 1-factor of G, then the set E (G)\E(M) is an edge-set of a 2-factor of G. T

FAQs

What is an H-coloring of a cubic multi-graph G?

An H-coloring is a mapping f from edges of G to edges of H such that, for each vertex v in G, the set of edges incident to v is mapped to the set of edges incident to some vertex x in H.

What does the Petersen coloring conjecture state?

For every bridgeless cubic graph G, the Petersen graph P10 satisfies P10 ≺ G under the Sylvester coloring relation.

What are S10 and S12 in the paper’s main results?

S10 is the smallest cubic multi-graph with no perfect matching (ten vertices). S12 is obtained from S10 by replacing its unique vertex adjacent to three bridges with a triangle.

Jul 16, 2026

Upload by River Wang