✦ LIBER ✦

Totally Critical Even Order Graphs

✍ Scribed by G.M. Hamilton; A.J.W. Hilton; H.R.F. Hind

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 138 KB
Volume: 76
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1999.1902

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is totally critical if it is Type 2, connected, and the removal of any edge reduces the total chromatic number. A good characterization of all totally critical graphs is unlikely as Sanchez-Arroyo showed that determining the total chromatic number of a graph is an NP-hard problem. In this paper we show that if the Conformability Conjecture is correct, then totally critical graphs of even order with maximum degree at least one half of their order are characterized by a simple equation involving the order, maximum degree, and deficiency of the graph and the edge independence number of the complement. We also show that if the maximum degree 2 of a non-conformable graph G of even order satisfies 1 2 |V | 2 3 4 |V | &1 then G is regular and has a simple structure.

📜 SIMILAR VOLUMES

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.

Chromatic Index Critical Graphs of Even

Chromatic Index Critical Graphs of Even Order with Five Major Vertices

✍ Zi-Xia Song; H. P. Yap 📂 Article 📅 2005 🏛 Springer Japan 🌐 English ⚖ 280 KB

Regular 4-critical graphs of even degree

✍ Andrey A. Dobrynin; Leonid S. Melnikov; Artem V. Pyatkin 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 237 KB 👁 1 views

## Abstract In 1960, Dirac posed the conjecture that __r__‐connected 4‐critical graphs exist for every __r__ ≥ 3. In 1989, Erdős conjectured that for every __r__ ≥ 3 there exist __r__‐regular 4‐critical graphs. In this paper, a technique of constructing __r__‐regular __r__‐connected vertex‐transiti

Stability Critical Graphs and Even Subdi

Stability Critical Graphs and Even Subdivisions of K4

✍ E.C. Sewell; L.E. Trotter 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 375 KB

Matchings in 3-vertex-critical graphs: T

Matchings in 3-vertex-critical graphs: The even case

✍ Nawarat Ananchuen; Michael D. Plummer 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

Chromatic index critical graphs of order

Chromatic index critical graphs of order 9

✍ Amanda G. Chetwynd; H.P. Yap 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 954 KB

We prove that a 2-connected graph of order 9 having maximum valency A 34 is chromatic index critical if and only if its valency-list is one of the following: 248, 3247 (except one graph), 258, 345 ', 4356, 26a, 356', 4267, 45266, 5465, 27', 367', 457', 46276, 52676, 56375, 6574, 57385, 6386, 627285,