✦ LIBER ✦

Circular Colouring and Orientation of Graphs

✍ Scribed by Xuding Zhu

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 88 KB
Volume: 86
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2002.2117

No coin nor oath required. For personal study only.

✦ Synopsis

This paper proves that if a graph G has an orientation D such that for each cycle C with djCj ðmod kÞ 2 f1; 2; . . . ; 2d À 1g we have jCj=jC þ j4k=d and jCj=jC À j4k=d; then G has a ðk; dÞ-colouring and hence w c ðGÞ4k=d: This is a generalization of a result of Tuza (J. Combin. Theory Ser. B 55 (1992), 236-243) concerning the vertex colouring of a graph, and is also a strengthening of a result of Goddyn et al. (J. Graph Theory 28 (1998), 155-161) concerning the relation between orientation and circular chromatic number of a graph. # 2002 Elsevier Science (USA)

📜 SIMILAR VOLUMES

Simultaneously Colouring the Edges and F

Simultaneously Colouring the Edges and Faces of Plane Graphs

✍ Adrian O. Waller 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 345 KB

In a simultaneous colouring of the edges and faces of a plane graph we colour edges and faces so that every two adjacent or incident pair of them receive different colours. In this paper we prove a conjecture of Mel'nikov which states that for this colouring every plane graph can be coloured with 2+

Orientation distance graphs

✍ Gary Chartrand; David Erwin; Michael Raines; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

For two nonisomorphic orientations D and D H of a graph G, the orientation distance d o (D,D H ) between D and D H is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D H . The orientation distance graph h o (G) of G has the set y(G) of pairwi

Circular choosability of graphs

✍ Xuding Zhu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) c;l ðGÞ of a graph G and prove that they are equivalent. Then we prove that for any graph G, c;l ðGÞ ! l ðGÞ À 1. Examples are given to show

Circular perfect graphs

✍ Xuding Zhu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB

For 1 d k, let K k=d be the graph with vertices 0; 1; . . . ; k À 1, in which i $ j if d ji À jj k À d. The circular chromatic number c ðGÞ of a graph G is the minimum of those k=d for which G admits a homomorphism to K k=d . The circular clique number ! c ðGÞ of G is the maximum of those k=d for wh

Circular permutation graphs

✍ D. Rotem; J. Urrutia 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 481 KB

Generalized Pigeonhole Properties of Gra

Generalized Pigeonhole Properties of Graphs and Oriented Graphs

✍ Anthony Bonato; Peter J Cameron; Dejan Delić; Stéphan Thomassé 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

A relational structure A satisfies the P(n, k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is isomorphic to A. The P(2, 1) property is just the pigeonhole property, (P), introduced by Cameron, and studied