Search

In this paper, we prove that every graph with average degree at least s + t + 2 has a vertex partition into two parts, such that one part has average degree at least s , and the other part has average degree at least t. This solves a conjecture of Csóka, Lo, Norin, Wu and Yepremyan. [ABSTRACT FROM AUTHOR]

It is well known that for any integers k and g, there is a graph with chromatic number at least k and girth at least g. In 1960s, Erdös and Hajnal conjectured that for any k and g, there exists a number h(k,g), such that every graph with chromatic number at least h(k,g) contains a subgraph with chromatic number at least k and girth at least g. In 1977, Rödl proved the case when $g=4$ , for arbitrary k. We prove the fractional chromatic number version of Rödl's result. [ABSTRACT FROM AUTHOR]

Abstract: Nash-Williams and Tutte independently characterized when a graph has k edge-disjoint spanning trees; a consequence is that 2k-edge-connected graphs have k edge-disjoint spanning trees. Kriesell conjectured a more general statement: defining a set to be j-edge-connected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2k-edge-connected in G, then G has k edge-disjoint trees containing S. Lap Chi Lau proved that the conclusion holds whenever S is 24k-edge-connected in G. We improve Lauʼs result by showing that it suffices for S to be 6.5k-edge-connected in G. This and an analogous result for packing stronger objects called “S-connectors” follow from a common generalization of the Tree Packing Theorem and Hakimiʼs criterion for orientations with specified outdegrees. We prove the general theorem using submodular functions and the Matroid Union Theorem. [Copyright &y& Elsevier]

Let ch ( G ) denote the choice number of a graph G (also called “list chromatic number” or “choosability” of G ). Noel, Reed, and Wu proved the conjecture of Ohba that ch ( G ) = χ ( G ) when | V ( G ) | ≤ 2 χ ( G ) + 1 . We extend this to a general upper bound: ch ( G ) ≤ max { χ ( G ) , ⌈ ( | V ( G ) | + χ ( G ) − 1 ) / 3 ⌉ } . Our result is sharp for | V ( G ) | ≤ 3 χ ( G ) using Ohba’s examples, and it improves the best-known upper bound for ch ( K 4 , … , 4 ) . [ABSTRACT FROM AUTHOR]

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) =X(G). Since X(G)α(G) ≥|V (G)|, Hadwiger's Conjecture implies that α(G)h(G) ≥ |V (G)|. We show that (2α(G)-[log τ(τα(G)/2)])h(G) ≥ |V (G)| where τ ∼ 6.83. For graphs with α(G) = 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V (G)| when α(G) = 3. [ABSTRACT FROM AUTHOR]