✦ LIBER ✦

Acrylic improper colorings of graphs

✍ Scribed by Boiron, P.; Sopena, E.; Vignal, L.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 153 KB
Volume: 32
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199909)32:1<97::aid-jgt9>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

In this article, we introduce the new notion of acyclic improper colorings of graphs. An improper coloring of a graph is a vertex-coloring in which adjacent vertices are allowed to have the same color, but each color class V i satisfies some condition depending on i. Such a coloring is acyclic if there are no alternating 2-colored cycles. We prove that every outerplanar graph can be acyclically 2-colored in such a way that each monochromatic subgraph has degree at most five and that this result is best possible. For planar graphs, we prove some negative results and state some open problems.

📜 SIMILAR VOLUMES

Oriented list colorings of graphs

✍ Zs. Tuza; M. Voigt 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

A 2-assignment on a graph G (V,E) is a collection of pairs Lv of allowed colors speci®ed for all vertices v PV. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satis®es the following property: For every 2-assignment there exists a choic

Extending colorings of locally planar gr

Extending colorings of locally planar graphs

✍ Michael O. Albertson; Joan P. Hutchinson 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

Suppose G is a graph embedded in S g with width (also known as edge width) at least 264(2 g À 1). If P V(G) is such that the distance between any two vertices in P is at least 16, then any 5-coloring of P extends to a 5-coloring of all of G. We present similar extension theorems for 6-and 7-chromati

Total colorings of planar graphs with la

Total colorings of planar graphs with large maximum degree

✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 2 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.

Construction of uniquelyH-colorable grap

Construction of uniquelyH-colorable graphs

✍ Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 2 views

We shall prove that for any graph H that is a core, if χ(G) is large enough, then H × G is uniquely H-colorable. We also give a new construction of triangle free graphs, which are uniquely n-colorable.

Coloring edges of embedded graphs

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

In this paper, we prove that any graph G with maximum degree ÁG ! 11 p 49À241AEa2, which is embeddable in a surface AE of characteristic 1AE 1 and satis®es jVGj b 2ÁGÀ5À2 p 6ÁG, is class one.

Optimal edge coloring of large graphs

✍ G�mez, J.; Escudero, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 2 views

Most of the general families of large considered graphs in the context of the so-called (⌬, D) problem-that is, how to obtain graphs with maximum order, given their maximum degree ⌬ and their diameter D-known up to now for any value of ⌬ and D, are obtained as product graphs, compound graphs, and ge