✦ LIBER ✦

Topological subgraphs of cubic graphs and a theorem of dirac

✍ Scribed by Richard Statman

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 339 KB
Volume: 6
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190060406

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The topological subgraph relation between cubic graphs is analyzed. The analysis is then applied to generalize a theorem of Dirac.

📜 SIMILAR VOLUMES

A dirac-type theorem for squares of grap

A dirac-type theorem for squares of graphs

✍ Tomasz Traczyk Jr. 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB

We prove that if G is a connected graph with p vertices and minimum degree greater than max( p/4 -1,3) then G2 is pancyclic. The result is best possible of its kind.

Extremal bipartite subgraphs of cubic tr

Extremal bipartite subgraphs of cubic triangle-free graphs

✍ Glenn Hopkins; William Staton 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB

## Abstract A cubic triangle‐free graph has a bipartite subgraph with at least 4/5 of the original edges. Examples show that this is a best possible result.

Interval coloring of (3,4)-biregular bip

Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs

✍ A. V. Pyatkin 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## Abstract An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph __G__ = (__A__,__B__;__E__) is (α, β)‐b

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

Proof of a Conjecture of Mader, Erdös an

Proof of a Conjecture of Mader, Erdös and Hajnal on Topological Complete Subgraphs

✍ B. Bollobás; A. Thomason 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 89 KB

We show that every graph G of size at least 256 p 2 |G| contains a topological complete subgraph of order p. This slight improvement of a recent result of Komlós and Szemerédi proves a conjecture made by Mader and by Erdös and Hajnal.

The minimum number of subgraphs in a gra

The minimum number of subgraphs in a graph and its complement

✍ Lane Clark 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB 👁 2 views

## Abstract For a graphb __F__ without isolated vertices, let __M__(__F__; __n__) denote the minimum number of monochromatic copies of __F__ in any 2‐coloring of the edges of __K__~__n__~. Burr and Rosta conjectured that when __F__ has order __t__, size __u__, and __a__ automorphisms. Independent