✦ LIBER ✦

Absolutely 3-chromatic graphs

✍ Scribed by Anthony B. Evans

Publisher: John Wiley and Sons
Year: 1986
Tongue: English
Weight: 421 KB
Volume: 10
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190100409

No coin nor oath required. For personal study only.

✦ Synopsis

A fold is a sequence of simple folds (elementary homomorphisms in which the identified vertices are both adjacent to a common vertex). It was shown in (C. R. Cook and A. B. Evans, Graph folding. Proceedings o f the South Eastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, 1979, pp. 305-314) that all connected n-chromatic graphs can be folded onto K,. A connected n-chromatic graph is called absolutely n-chromatic if it can only be folded onto K, , , when rn = n. Some classes of absolutely n-chromatic graphs were given in Cook and Evans. In this paper, w e classify the absolutely 3-chromatic graphs.

LIJ'(G) is the largest value of m for which there exists a fold of G onto K,,, .

📜 SIMILAR VOLUMES

4-chromatic projective graphs

✍ Youngs, D. A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 464 KB

We construct a family of 4-chromatic graphs which embed on the projective plane, and characterize the edge-critical members. The family includes many well known graphs, and also a new sequence of graphs, which serve to improve Gallai's bound on the length of the shortest odd circuit in a 4-chromatic

On chromatic-choosable graphs

✍ Kyoji Ohba 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 70 KB

## Abstract A graph is chromatic‐choosable if its choice number coincides with its chromatic number. It is shown in this article that, for any graph __G__, if we join a sufficiently large complete graph to __G__, then we obtain a chromatic‐choosable graph. As a consequence, if the chromatic number

Maximal σ-polynomials of connected 3-chr

Maximal σ-polynomials of connected 3-chromatic graphs

✍ Ioan Tomescu 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 113 KB 👁 1 views

## Abstract In the set of graphs of order __n__ and chromatic number __k__ the following partial order relation is defined. One says that a graph __G__ is less than a graph __H__ if __c__~__i__~(__G__) ≤ __c__~__i__~(__H__) holds for every __i__, __k__ ≤ __i__ ≤ __n__ and at least one inequality is

Chromaticity of triangulated graphs

✍ Paul Vaderlind 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

A graph G is called triangulated (or rigid-circuit graph, or chordal graph) if every circuit of G with length greater than 3 has a chord. It can be shown (see, UI, . . . , u,, . Let G = G,.

Path chromatic numbers of graphs

✍ Jin Akiyama; Hiroshi Era; Severino V. Gervacio; Mamoru Watanabe 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

Circular chromatic index of graphs of ma

Circular chromatic index of graphs of maximum degree 3

✍ Peyman Afshani; Mahsa Ghandehari; Mahya Ghandehari; Hamed Hatami; Ruzbeh Tusserk 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract This paper proves that if __G__ is a graph (parallel edges allowed) of maximum degree 3, then χ′~__c__~(__G__) ≤ 11/3 provided that __G__ does not contain __H__~1~ or __H__~2~ as a subgraph, where __H__~1~ and __H__~2~ are obtained by subdividing one edge of __K__ (the graph with three