✦ LIBER ✦

A generalized construction of chromatic index critical graphs from bipartite graphs

✍ Scribed by Michael Plantholt

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 378 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090309

No coin nor oath required. For personal study only.

✦ Synopsis

W e prove that any graph with maximum degree n which can be obtained by removing exactly 2n -1 edges from the join K? -K, ,, is n-critical This generalizes special constructions of critical graphs by S Fiorini and H P Yap, and suggests a possible extension of another general construction due to Yap

1. Introduction

Given any simple graph G. we denote its vertex set and edge set by V ( C ) and E(G), respectively. We denote by d(u, G ) the degree of vertex u in G. For any subset X of V ( G ) , let G -X denote the subgraph of G induced by the vertex set V(G)\X. The.join of two disjoint graphs GI and G, denoted GI + G , has vertex set V ( G l ) U V ( G 2 ) and edge set

For all other basic terminology and notation, we follow Harary [6].

An (edge) coloring of a graph G is an assignment of colors to its edges such that no two adjacent edges are assigned the same color. The chrotnnric index x'(G) of G is the minimum number of colors used among all colorings of G. A classic theorem of Vizing [ l o ] states that if G has maximum

📜 SIMILAR VOLUMES

A construction of chromatic index critic

A construction of chromatic index critical graphs

✍ Hian Poh Yap 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

## Abstract We prove that if __K__ is an undirected, simple, connected graph of even order which is of class one, regular of degree __p__ ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph __G__ obtained from __K__ by splitting any vertex is __p

Chromatic-index-critical graphs of even

Chromatic-index-critical graphs of even order

✍ Gr�newald, Stefan; Steffen, Eckhard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 2 views

A k-critical (multi-) graph G has maximum degree k, chromatic index χ (G) = k + 1, and χ (G -e) < k + 1 for each edge e of G. For each k ≥ 3, we construct k-critical (multi-) graphs with certain properties to obtain counterexamples to some well-known conjectures.

Constructions of bipartite graphs from f

Constructions of bipartite graphs from finite geometries

✍ Keith E. Mellinger; Dhruv Mubayi 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 1 views

## Abstract We construct an incidence structure using certain points and lines in finite projective spaces. The structural properties of the associated bipartite incidence graphs are analyzed. These __n__ × __n__ bipartite graphs provide constructions of __C__~6~‐free graphs with Ω(__n__^4/3^ edges

Chromatic-Index-Critical Graphs of Order

Chromatic-Index-Critical Graphs of Orders 11 and 12

✍ G Brinkmann; E Steffen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 177 KB

A chromatic-index-critical graph G on n vertices is non-trivial if it has at most n 2 edges. We prove that there is no chromatic-index-critical graph of order 12, and that there are precisely two non-trivial chromatic-index-critical graphs on 11 vertices. Together with known results this implies tha

The chromatic index of complete multipar

The chromatic index of complete multipartite graphs

✍ D. G. Hoffman; C. A. Rodger 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

## Abstract We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index.

The chromatic index of graphs with a spa

The chromatic index of graphs with a spanning star

✍ Mike Plantholt 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 468 KB 👁 1 views

## Abstract Vizing's Theorem states that any graph __G__ has chromatic index either the maximum degree Δ(__G__) or Δ(__G__) + 1. If __G__ has 2~s~ + 1 points and Δ(__G__) = 2s, a well‐known necessary condition for the chromatic index to equal 2~s~ is that __G__ have at most 2s^2^ lines. Hilton conj