Nacionalni portal odprte znanosti

6-decomposition of snarks

It is known that smallest counterexamples to the Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture (if they exist) are cyclically 4- and 5-edge-connected, respectively. We further analyse small cycle separating cuts in possible counterexamples. We prove that if a smallest counterexample G ...

A ▫${\ strong edge-coloring}$▫ of a graph is a proper edge-coloring, in which the edges of every path of length ▫$3$▫ receive distinct colors; in other words, every pair of edges at distance at most ▫$2$▫ must be colored differently. The least number of colors needed for a strong edge-coloring of a ...

We introduce a new invariant of a cubic graph – its regular colouring defect – which is defined as the smallest number of edges left uncovered by any collection of three perfect matchings that have no edge in common. This invariant is a modification of colouring defect, an invariant introduced by St ...