Search

Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley-Wilf limits. We investigate the maximum number of edges in [ABSTRACT FROM AUTHOR]

We prove a conjecture of Ohba that says that every graph G on at most [ABSTRACT FROM AUTHOR]

For a loopless multigraph G, the fractional arboricity Arb( G) is the maximum of [ABSTRACT FROM AUTHOR]

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]

Abstract: It is shown that every -edge-connected graph G has a mod -orientation, and that a -regular graph G has a mod -orientation if and only if has a partition such that , These extend former results by Da Silva and Dahab on nowhere zero 3-flows of 5-regular graphs, and by Lai and Zhang on highly connected graphs with nowhere zero 3-flows. [Copyright &y& Elsevier]

Abstract: Thomassen conjectured that every 4-connected line graph is Hamiltonian. A vertex cut X of G is essential if has at least two non-trivial components. We prove that every 3-connected, essentially 11-connected line graph is Hamiltonian. Using Ryjáček''s line graph closure, it follows that every 3-connected, essentially 11-connected claw-free graph is Hamiltonian. [Copyright &y& Elsevier]