Search

Let ϕc(G) be the circular flow number of a bridgeless graph G. By Steffen it was proved that, for a bridgeless (2t+1)‐regular graph G, where t≥1 is a positive integer, ϕc(G)∈{2+1t,2+22t−1} if and only if G has a perfect matching M such that G−M is bipartite. This implies that G is a class 1 graph. For t=1, all graphs with circular flow number bigger than 4 are class 2 graphs. We show that, for all t≥1, 2+22t−1=inf{ϕc(G):G is a (2t+1)‐regular class 2 graph}. This was conjectured to be true by Steffen. Moreover we prove that, for all t≥1, inf{ϕc(G):G is a (2t+1)‐regular class 1 graph with no perfect matching whose removal leaves a bipartite graph=2+22t−1. We further disprove the conjecture that every (2t+1)‐regular class 1 graph has circular flow number at most 2+2t. [ABSTRACT FROM AUTHOR]

We construct highly edge‐connected r‐regular graphs of even order which do not contain r−2 pairwise disjoint perfect matchings. When r is a multiple of 4, the result solves a problem of Thomassen [4]. [ABSTRACT FROM AUTHOR]

Let [ABSTRACT FROM AUTHOR]

Tutte's 5-flow conjecture from 1954 states that every bridgeless graph has a nowhere-zero 5-flow. It suffices to prove the conjecture for cyclically 6-edge-connected cubic graphs. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. This implies that every minimum counterexample to the 5-flow conjecture has oddness at least 6. [ABSTRACT FROM AUTHOR]

Let G be a bridgeless cubic graph. Consider a list of k 1-factors of G. Let [ABSTRACT FROM AUTHOR]

The article characterizes [ABSTRACT FROM AUTHOR]

Let G be a bridgeless cubic graph. Consider a list of k 1-factors of G. Let [ABSTRACT FROM AUTHOR]

This article determines the set of the circular flow numbers of regular graphs. Let [ABSTRACT FROM AUTHOR]

A graph G is class II, if its chromatic index is at least δ + 1. Let H be a maximum δ-edge-colorable subgraph of G. The paper proves best possible lower bounds for | E( H)|/| E( G)|, and structural properties of maximum δ-edge-colorable subgraphs. It is shown that every set of vertex-disjoint cycles of a class II graph with δ≥3 can be extended to a maximum δ-edge-colorable subgraph. Simple graphs have a maximum δ-edge-colorable subgraph such that the complement is a matching. Furthermore, a maximum δ-edge-colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory [ABSTRACT FROM AUTHOR]

In 1968 Vizing conjectured that any independent vertex set of an edge-chromatic critical graph G contains at most half of the vertices of G, that is, α(G≤½(G)). Let Δ be the maximum vertex degree in a critical graph. For each Δ, we determine c(Δ) such that α(G)≤c(Δ)V). 1991 Mathematics Subject Classification 05C15, 05C70. [ABSTRACT FROM AUTHOR]