All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 21

Showing per page

Bounded expansion in web graphs

Silvia Gago, Dirk Schlatter (2009)

Commentationes Mathematicae Universitatis Carolinae

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.

Complete minors, independent sets, and chordal graphs

József Balogh, John Lenz, Hehui Wu (2011)

Discussiones Mathematicae Graph Theory

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.

Defective choosability of graphs in surfaces

Douglas R. Woodall (2011)

Discussiones Mathematicae Graph Theory

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...

Graphic Splitting of Cographic Matroids

Naiyer Pirouz (2015)

Discussiones Mathematicae Graph Theory

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.

On a special case of Hadwiger's conjecture

Michael D. Plummer, Michael Stiebitz, Bjarne Toft (2003)

Discussiones Mathematicae Graph Theory

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.

The contractible subgraph of 5 -connected graphs

Chengfu Qin, Xiaofeng Guo, Weihua Yang (2013)

Czechoslovak Mathematical Journal

An edge e of a k -connected graph G is said to be k -removable if G - e is still k -connected. A subgraph H of a k -connected graph is said to be k -contractible if its contraction results still in a k -connected graph. A k -connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k -connected. In this paper, we show that there is a contractible subgraph in a 5 -connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor...

Currently displaying 1 – 20 of 21

Page 1 Next