✦ LIBER ✦

On the Number of Edges in Colour-Critical Graphs and Hypergraphs

✍ Scribed by A. V. Kostochka; M. Stiebitz

Publisher: Springer-Verlag
Year: 2000
Tongue: English
Weight: 189 KB
Volume: 20
Category: Article
ISSN: 0209-9683
DOI: 10.1007/s004930070005

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the Number of Edges in Hypergraphs Cr

On the Number of Edges in Hypergraphs Critical with Respect to Strong Colourings

✍ Alexandr V. Kostochka; Douglas R. Woodall 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 94 KB

A colouring of the vertices of a hypergraph G is called strong if, for every edge A, the colours of all vertices in A are distinct. It corresponds to a colouring of the generated graph (G) obtained from G by replacing every edge by a clique. We estimate the minimum number of edges possible in a k-cr

A list version of Dirac's theorem on the

A list version of Dirac's theorem on the number of edges in colour-critical graphs

✍ Alexandr V. Kostochka; Michael Stiebitz 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 2 views

## Abstract One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 (1941) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension o

The independence number of an edge-chrom

The independence number of an edge-chromatic critical graph

✍ Douglas R. Woodall 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB 👁 1 views

A graph G with maximum degree and edge chromatic number (G)> is edge--critical if (G -e) = for every edge e of G. It is proved here that the vertex independence number of an edge--critical graph of order n is less than 3 5 n. For large , this improves on the best bound previously known, which was ro

Edge search in graphs and hypergraphs of

Edge search in graphs and hypergraphs of bounded rank

✍ Ingo Althöfer; Eberhard Triesch 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 512 KB

Althofer, 1. and E. Triesch, Edge search in graphs and hypergraphs of bounded rank, Discrete Mathematics 115 (1993) l-9.

On the maximum number of independent edg

On the maximum number of independent edges in cubic graphs

✍ Arthur M. Hobbs; Edward Schmeichel 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 146 KB

Let the reals be extended to include oo with o~ > r

On the extremal number of edges in hamil

On the extremal number of edges in hamiltonian connected graphs

✍ Tung-Yang Ho; Cheng-Kuan Lin; Jimmy J.M. Tan; D. Frank Hsu; Lih-Hsing Hsu 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 421 KB

a b s t r a c t Assume that n and δ are positive integers with 3 ≤ δ < n. Let hc(n, δ) be the minimum number of edges required to guarantee an n-vertex graph G with minimum degree δ(G) ≥ δ to be hamiltonian connected.