On sublinear approximations for the Petersen coloring conjecture

zbMATH Open1472.05057arXiv2104.09241MaRDI QIDQ4959474FDOQ4959474

Authors: Davide Mattiolo, Vahan V. Mkrtchyan, G. Mazzuoccolo

Publication date: 13 September 2021

Abstract: If

f : m a t h b b N i g h t a r r o w m a t h b b N

is a function, then let us say that

f

is sublinear if [lim_{n ightarrow +infty}frac{f(n)}{n}=0.] If

G = (V, E)

is a cubic graph and

c : E i g h t a r r o w 1, ..., k

is a proper

k

-edge-coloring of

G

, then an edge

e = u v

of

G

is poor (rich) in

c

, if the edges incident to

u

and

v

are colored with three (five) colors. An edge is abnormal if it is neither rich nor poor. The Petersen coloring conjecture of Jaeger states that any bridgeless cubic graph admits a proper 5-edge-coloring

c

, such that there is no an abnormal edge of

G

with respect to

c

. For a proper 5-edge-coloring

c

of

G

, let

N_{G} (c)

be the set of abnormal edges of

G

with respect to

c

. In this paper we show that (a) The Petersen coloring conjecture is equivalent to the statement that there is a sublinear function

f : m a t h b b N i g h t a r r o w m a t h b b N

, such that all bridgeless cubic graphs admit a proper 5-edge-coloring

c

with

| N_{G} (c) | l e q f (| V |)

; (b) for

k = 2, 3, 4

, the statement that there is a sublinear function

f : m a t h b b N i g h t a r r o w m a t h b b N

, such that all (cyclically)

k

-edge-connected cubic graphs admit a proper 5-edge-coloring

c

with

| N_{G} (c) | l e q f (| V |)

is equivalent to the statement that all (cyclically)

k

-edge-connected cubic graphs admit a proper 5-edge-coloring

c

with

| N_{G} (c) | l e q 2 k + 1

.

Full work available at URL: https://arxiv.org/abs/2104.09241

Recommendations

zbMATH Keywords

cubic graph normal edge-coloring Petersen coloring conjecture abnormal edge

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cited In (4)

This page was built for publication: On sublinear approximations for the Petersen coloring conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4959474)