✦ LIBER ✦

Overfull conjecture for graphs with high minimum degree

✍ Scribed by Michael Plantholt

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 79 KB
Volume: 47
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20013

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Chetwynd and Hilton showed that any regular graph G of even order n which has relatively high degree $\Delta (G),\ge,((\sqrt{7}- 1)/2), n$ has a 1‐factorization. This is equivalent to saying that under these conditions G has chromatic index equal to its maximum degree $\Delta(G)$. Using this result, we show that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree $\delta(G),\ge,(\sqrt{7}/3),n$ has chromatic index equal to its maximum degree providing that G does not contain an “overfull” subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 73–80, 2004

📜 SIMILAR VOLUMES

Subdivisions of graphs with large minimu

Subdivisions of graphs with large minimum degree

✍ Carsten Thomassen 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 1 views

Minimum degree thresholds for bipartite

Minimum degree thresholds for bipartite graph tiling

✍ Albert Bush; Yi Zhao 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 361 KB

## Abstract Given a bipartite graph __H__ and a positive integer __n__ such that __v__(__H__) divides 2__n__, we define the minimum degree threshold for bipartite __H__‐tiling, δ~2~(__n, H__), as the smallest integer __k__ such that every bipartite graph __G__ with __n__ vertices in each partition

Total domination in graphs with minimum

Total domination in graphs with minimum degree three

✍ Favaron, Odile; Henning, Michael A.; Mynhart, Christina M.; Puech, Jo�l 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 3 views

A set S of vertices of a graph G is a total dominating set, if every vertex of V (G) is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at leas

Cycle lengths in graphs with large minim

Cycle lengths in graphs with large minimum degree

✍ V. Nikiforov; R. H. Schelp 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

## Abstract Our main result is the following theorem. Let __k__ ≥ 2 be an integer, __G__ be a graph of sufficiently large order __n__, and __δ__(__G__) ≥ __n__/__k__. Then: __G__ contains a cycle of length __t__ for every even integer __t__ ∈ [4, __δ__(__G__) + 1]. If __G__ is nonbipartite then

Bounds related to domination in graphs w

✍ Sanchis, Laura A. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 2 views

A dominating set for a graph G = (V, E) is a subset of vertices V ⊆ V such that for all v ∈ V -V there exists some u ∈ V for which {v, u} ∈ E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q e

Graph decomposition with constraints on

Graph decomposition with constraints on the connectivity and minimum degree

✍ Carsten Thomassen 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

## Abstract For each pair __s,t__ of natural numbers there exist natural numbers __f(s,t)__ and __g(s,t)__ such that the vertex set of each graph of connectivity at least __f(s,t)__ (respectively minimum degree at least __g(s,t))__ has a decomposition into sets which induce subgraphs of connectivit