✦ LIBER ✦

UniquelyH-colorable graphs with large girth

✍ Scribed by Zhu, Xuding

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 498 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199609)23:1<33::aid-jgt3>3.0.co;2-l

No coin nor oath required. For personal study only.

✦ Synopsis

Suppose G and H are graphs. We say G is H-colorable if there is a homomorphism (edge-preserving vertex mapping) from G to H. We say a graph G is uniquely H-colorable if there is an onto homomorphism c from G to H, and any other homomorphism from G to H is the composition o o c of c with an automorphism o of H. In case H is the complete graph K,, the notion of uniquely H-colorable coincides with that of uniquely n-colorable. It was proved by B. Bollobas and N. Sauer that for any integer n there are graphs of arbitrary large girth which are uniquely n-colorable. We generalize this result and prove that for any graph H which is a core (1.e.. H admits no homomorphisms to any of its proper subgraphs), and for any integer g, there is a graph which is uniquely Hcolorable and has girth at least g. We then use this generalization to answer a question concerning the star-chromatic number of a graph. A graph G is said to be ( k , d)-colorable if there is a coloring c of the vertices of G with k colors (0, I , . . . , k -1) such that d 5 I . ( . ) -c(y)l 5 kd for every edge (rc, y) of G. The star-chromatic number of G is the infimum of the ratio k / d such that G is (k,d)-colorable. ~e shall show that for any rational k / d 2 2, there are graphs G of arbitrary large girth with star-chromatic number x*(G) = k / d . In particular, for any integer n, there are graphs G of arbitrary large girth with x* (G) = x ( G ) = n.

📜 SIMILAR VOLUMES

Construction of uniquelyH-colorable grap

Construction of uniquelyH-colorable graphs

✍ Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 1 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.

(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 👁 2 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

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs with large girth

✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)

Optimal edge coloring of large graphs

✍ G�mez, J.; Escudero, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 1 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

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.

Decomposing graphs with girth at least f

Decomposing graphs with girth at least five under degree constraints

✍ Diwan, Ajit A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

We prove that the vertex set of a simple graph with minimum degree at least s + t -1 and girth at least 5 can be decomposed into two parts, which induce subgraphs with minimum degree at least s and t, respectively, where s, t are positive integers ≥ 2.