✦ LIBER ✦

Subdivisions and the chromatic index of r-graphs

✍ Scribed by K. Kilakos; F. B. Shepherd

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 625 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199607)22:3<203::aid-jgt1>3.0.co;2-q

No coin nor oath required. For personal study only.

✦ Synopsis

Let T2 be the graph obtained from the Petersen graph by first deleting a vertex and then contracting an edge incident to a vertex of degree two. We give a simple characterization of the graphs that contain no subdivision of T2. This characterization is used to show that if every planar r-graph is r-edge colorable, then every r-graph with no subdivision of T2 is r-edge colorable. 0 1996 John Wiley & Sons, Inc. I Conjecture 1.2. Every r-graph with no subdivision of the Petersen graph (see Figure 1) Historically, Conjectures 1.1 and 1.2 date back to the famous Four Colour Problem. Consider the special case when r = 3. Then Conjecture 1.1 is Tait's [12] equivalent formulation of the Four Colour Problem and Conjecture 1.2 is Tutte's [14] generalization of

📜 SIMILAR VOLUMES

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.

Strong chromatic index of subset graphs

✍ Quinn, Jennifer J.; Benjamin, Arthur T. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph S m (k, l) is a bipartite graph whose vertices are the kand l-subsets of an m element ground set where two vertices ar

On the oriented chromatic index of orien

On the oriented chromatic index of oriented graphs

✍ Pascal Ochem; Alexandre Pinlou; Éric Sopena 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

## Abstract A homomorphism from an oriented graph __G__ to an oriented graph __H__ is a mapping $\varphi$ from the set of vertices of __G__ to the set of vertices of __H__ such that $\buildrel {\longrightarrow}\over {\varphi (u) \varphi (v)}$ is an arc in __H__ whenever $\buildrel {\longrightarrow}

The strong chromatic index of C4-free gr

The strong chromatic index of C4-free graphs

✍ Mohammad Mahdian 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 1 views

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.

Game chromatic index of k-degenerate gra

Game chromatic index of k-degenerate graphs

✍ Leizhen Cai; Xuding Zhu 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 1 views