✦ LIBER ✦

Color-Critical Graphs on a Fixed Surface

✍ Scribed by Carsten Thomassen

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 420 KB
Volume: 70
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.1722

No coin nor oath required. For personal study only.

✦ Synopsis

dedicated to professor w. t. tutte on the occasion of his eightieth birthday

Let S be an orientable surface other than the sphere and let k be a natural number. Then there are infinitely many k-color-critical graphs on S if and only if 3 k 5. In particular, if k 5, then there exists a polynomially bounded algorithm for deciding if a graph on S can be k-colored. We extend this to the case where a subgraph of fixed cardinality is precolored. We also establish a corresponding list-color theorem.

📜 SIMILAR VOLUMES

Long Cycles in Graphs on a Fixed Surface

✍ Thomas Böhme; Bojan Mohar; Carsten Thomassen 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 117 KB

We prove that there exists a function a: N 0 × R + Q N such that (i) If G is a 4-connected graph of order n embedded on a surface of Euler genus g such that the face-width of G is at least a(g, e), then G can be covered by two cycles each of which has length at least (1 -e) n. We apply this to deri

Coloring Locally Bipartite Graphs on Sur

Coloring Locally Bipartite Graphs on Surfaces

✍ Bojan Mohar; Paul D. Seymour 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 129 KB

It is proved that there is a function f: N Q N such that the following holds. Let G be a graph embedded in a surface of Euler genus g with all faces of even size and with edge-width \ f(g). Then (i) If every contractible 4-cycle of G is facial and there is a face of size > 4, then G is 3-colorable.

Coloring Face-Hypergraphs of Graphs on S

Coloring Face-Hypergraphs of Graphs on Surfaces

✍ André Kündgen; Radhika Ramamurthi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 223 KB

The face-hypergraph, H(G), of a graph G embedded in a surface has vertex set V(G), and every face of G corresponds to an edge of H(G) consisting of the vertices incident to the face. We study coloring parameters of these embedded hypergraphs. A hypergraph is k-colorable (k-choosable) if there is a c

A note on defective colorings of graphs

A note on defective colorings of graphs in surfaces

✍ Dan Archdeacon 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 2 views

A graph is (rn, k)-colorable if its vertices can be colored with rn colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. In a recent paper Cowen. Cowen, and Woodall proved that, for each compact surface S, there exists an integer k = k(S) such that eve

The number of defective colorings of gra

The number of defective colorings of graphs on surfaces

✍ Tom Rackham 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 1 views

A (k, 1)-coloring of a graph is a vertex-coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least c n distinct (4, 1)-colorings, where c is constant and ≈ 1.466 satisfies 3 = 2 +1. On the other hand for any >0, we gi

A Note on Graph Colorings and Graph Poly

A Note on Graph Colorings and Graph Polynomials

✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using