P. E. Haxell

We give a complete description of the set of triples (a,b,c) of real numbers with the following property. There exists a constant K such that a n_3 + b n_2 + c n_1 - K is a lower bound for the matching number of every connected subcubic graph G, where n_i denotes the number of vertices of degree i for each i.

A subgraph of a hypergraph H is even if all its degrees are positive even integers, and b-bounded if it has maximum degree at most b. Let f_b(n) denote the maximum number of edges in a linearn-vertex 3-uniform hypergraph which does not contain a b-bounded even subgraph. In this paper, we show that if b ≥ 12, then for some absolute constant B, thus establishing f_b(n) up to polylogarithmic factors. This leaves open the interesting case b = 2, which is the case of 2-regular subgraphs. We are able to show for some constants c, C > 0 that We conjecture that f₂(n) = n^{1 + o(1)} as n → ∞.

We consider multigraphs G for which equality holds in Vizing's classical edge colouring bound χ′(G)≤Δ + µ, where Δ denotes the maximum degree and µ denotes the maximum edge multiplicity of G. We show that if µ is bounded below by a logarithmic function of Δ, then G attains Vizing's bound if and only if there exists an odd subset S⊆V(G) with |S|≥3, such that |E[S]|>((|S| − 1)/2)(Δ + µ − 1). The famous Goldberg–Seymour conjecture states that this should hold for all µ≥2. We also prove a similar result concerning the edge colouring bound χ′(G)≤Δ + ⌈µ/⌊g/2⌋⌉, due to Steffen (here g denotes the girth of the underlying graph). Finally we give a general approximation towards the Goldberg‐Seymour conjecture in terms of Δ and µ. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:160‐168, 2012

LetC⁽³⁾_ndenote the 3-uniformtight cycle, that is, the hypergraph with verticesv₁, .–.–.,v_nand edgesv₁v₂v₃,v₂v₃v₄, .–.–.,v_n−1v_nv₁,v_nv₁v₂. We prove that the smallest integerN=N(n) for which every red–blue colouring of the edges of the complete 3-uniform hypergraph withNvertices contains a monochromatic copy ofC⁽³⁾_nis asymptotically equal to 4n/3 ifnis divisible by 3, and 2notherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rödl.