In this paper we study various models for web graphs with respect to bounded expansion. All the deterministic models even have constant expansion, whereas the copying model has unbounded expansion. The most interesting case turns out to be the preferential attachment model --- which we conjecture to have unbounded expansion, too.
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) ≥ χ(G). Since χ(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.
It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic ε, and k and d are positive integers such that k ≥ 3 and d is sufficiently large in terms of k and ε, then G is (k,d)*-colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved for list colorings...
In this paper, we obtain a forbidden minor characterization of a cographic matroid M for which the splitting matroid Mx,y is graphic for every pair x, y of elements of M.
Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.
An edge of a -connected graph is said to be -removable if is still -connected. A subgraph of a -connected graph is said to be -contractible if its contraction results still in a -connected graph. A -connected graph with neither removable edge nor contractible subgraph is said to be minor minimally -connected. In this paper, we show that there is a contractible subgraph in a -connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor...