✦ LIBER ✦

Coloring graphs with no odd-K4

✍ Scribed by Wenan Zang

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 350 KB
Volume: 184
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00090-3

No coin nor oath required. For personal study only.

✦ Synopsis

The purpose of this note is to present a polynomial-time algorithm which, given an arbitrary graph G as its input, finds either a proper 3-coloring of G or an odd-K4 that is a subgraph of G in time O(mn), where m and n stand for the number of edges and the number of vertices of G, respectively. (~

📜 SIMILAR VOLUMES

Coloring perfect (K4 − e)-free graphs

✍ Alan Tucker 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 349 KB

(2 + ?)-Coloring of planar graphs with l

(2 + ?)-Coloring of planar graphs with large odd-girth

✍ Klostermeyer, William; Zhang, Cun Quan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 3 views

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. N

K4-free graphs with no odd hole: Even pa

K4-free graphs with no odd hole: Even pairs and the circular chromatic number

✍ Yori Zwols 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K 4 -free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K 4 -free graph with no odd hole has

Online coloring graphs with high girth a

Online coloring graphs with high girth and high odd girth

✍ J. Nagy-György 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 243 KB

Graphs with k odd cycle lengths

✍ A. Gyárfás 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 481 KB

Gyarf&, A., Graphs with k odd cycle lengths, Discrete Mathematics 103 (1992) 41-48. If G is a graph with k z 1 odd cycle lengths then each block of G is either KZk+2 or contains a vertex of degree at most 2k. As a consequence, the chromatic number of G is at most 2k + 2. For a graph G let L(G) deno

Complexity of clique-coloring odd-hole-f

Complexity of clique-coloring odd-hole-free graphs

✍ David Défossez 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐c