✦ LIBER ✦

Coloring Locally Bipartite Graphs on Surfaces

✍ Scribed by Bojan Mohar; Paul D. Seymour

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 129 KB
Volume: 84
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2086

No coin nor oath required. For personal study only.

✦ Synopsis

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.

(ii) If G is a quadrangulation, then G is not 3-colorable if and only if there exist disjoint surface separating cycles C 1 , ..., C g such that, after cutting along C 1 , ..., C g , we obtain a sphere with g holes and g Möbius strips, an odd number of which is nonbipartite.

If embeddings of graphs are represented combinatorially by rotation systems and signatures [5], then the condition in (ii) is satisfied if and only if the geometric dual of G has an odd number of edges with negative signature.

📜 SIMILAR VOLUMES

Edge-Coloring Bipartite Graphs

✍ Ajai Kapoor; Romeo Rizzi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 65 KB

Given a bipartite graph G with n nodes, m edges, and maximum degree ⌬, we Ž . find an edge-coloring for G using ⌬ colors in time T q O m log ⌬ , where T is the time needed to find a perfect matching in a k-regular bipartite graph with Ž . O m edges and k F ⌬. Together with best known bounds for T th

Star coloring bipartite planar graphs

✍ H. A. Kierstead; André Kündgen; Craig Timmons 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

## Abstract A __star coloring__ of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eig

Balanced coloring of bipartite graphs

✍ Uriel Feige; Shimon Kogan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract Given a bipartite graph __G__(__U__∪__V, E__) with __n__ vertices on each side, an independent set __I__∈__G__ such that |__U__∩__I__|=|__V__∩__I__| is called a balanced bipartite independent set. A balanced coloring of __G__ is a coloring of the vertices of __G__ such that each color c

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

3-Coloring graphs embedded in surfaces

✍ Zhao, Yue 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB 👁 3 views

In this article, we show that there exists an integer k(Σ)

Minimum Color Sum of Bipartite Graphs

✍ Amotz Bar-Noy; Guy Kortsarz 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 242 KB

The problem of minimum color sum of a graph is to color the vertices of the Ž . graph such that the sum average of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated within 1y ⑀ Ž n , for any ⑀ ) 0, unless NP s ZPP Bar-Noy et al., Informa