✦ LIBER ✦

Graphs with full rank 3-color matrix and few 3-colorings

✍ Scribed by Serguei Norine; Jean-Sébastien Sereni

Book ID: 108167442
Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 69 KB
Volume: 98
Category: Article
ISSN: 0095-8956
DOI: 10.1016/j.jctb.2007.12.001

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Uniquely Edge-3-Colorable Graphs and Sna

Uniquely Edge-3-Colorable Graphs and Snarks

✍ John L. Goldwasser; Cun-Quan Zhang 📂 Article 📅 2000 🏛 Springer Japan 🌐 English ⚖ 164 KB

Equitable Total Coloring of Graphs with

Equitable Total Coloring of Graphs with Maximum Degree 3

✍ Wei-Fan Wang 📂 Article 📅 2002 🏛 Springer Japan 🌐 English ⚖ 120 KB

Color-critical graphs and hypergraphs wi

Color-critical graphs and hypergraphs with few edges and no short cycles

✍ H.L. Abbott; D.R. Hare; B. Zhou 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 378 KB

We give constructions of color-critical graphs and hypergraphs with no cycles of length 5 or shorter and with relatively few edges.

Drawing Colored Graphs with Constrained

Drawing Colored Graphs with Constrained Vertex Positions and Few Bends per Edge

✍ Emilio Di Giacomo; Giuseppe Liotta; Francesco Trotta 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 650 KB

Almost all graphs with average degree 4

Almost all graphs with average degree 4 are 3-colorable

✍ Dimitris Achlioptas; Cristopher Moore 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 323 KB

We analyze a randomized version of the Brelaz heuristic on sparse random graphs. We prove that almost all graphs with average degree dp4:03; i.e., Gðn; p ¼ d=nÞ; are 3-colorable and that a constant fraction of all 4-regular graphs are 3-colorable.

The 3-Colorability Problem on Graphs wit

The 3-Colorability Problem on Graphs with Maximum Degree Four

✍ Kochol, Martin; Lozin, Vadim; Randerath, Bert 📂 Article 📅 2003 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 189 KB