✦ LIBER ✦

Circular choosability

✍ Scribed by Frédéric Havet; Ross J. Kang; Tobias Müller; Jean-Sébastien Sereni

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 313 KB
Volume: 61
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20375

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We study circular choosability, a notion recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that cch(G)=O(ch(G)+ln|V(G)|) for every graph G. We investigate a generalization of circular choosability, the circular f‐choosability, where f is a function of the degrees. We also consider the circular choice number of planar graphs. Mohar asked for the value of τ ≔ sup{cch(G) : G is planar}, and we prove that 6≤τ≤8, thereby providing a negative answer to another question of Mohar. We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 241–270, 2009

📜 SIMILAR VOLUMES

Circular consecutive choosability of k-c

Circular consecutive choosability of k-choosable graphs

✍ Daphne Liu,; Serguei Norine,; Zhishi Pan;; Xuding Zhu 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB

Let S(r ) denote a circle of circumference r. The circular consecutive choosability ch cc (G) of a graph G is the least real number t such that

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 choosability via combinatorial

Circular choosability via combinatorial Nullstellensatz

✍ Serguei Norine; Tsai-Lien Wong; Xuding Zhu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB

## Abstract A __p__‐list assignment __L__ of a graph __G__ assigns to each vertex __v__ of __G__ a set ${{L}}({{v}})\subseteq \{{{0}}{{,}} {{1}}{{,}}\ldots{{,}}\, {{p}}-{{1}}\}$ of permissible colors. We say __G__ is __L__‐(__P__, __q__)‐colorable if __G__ has a (__P__, __q__)‐coloring __h__ such t

On two questions about circular choosabi

On two questions about circular choosability

✍ Serguei Norine 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract We answer two questions of Zhu on circular choosability of graphs. We show that the circular list chromatic number of an even cycle is equal to 2 and give an example of a graph for which the infimum in the definition of the circular list chromatic number is not attained. © 2008 Wiley Pe

Choosability, Edge Choosability, and Tot

Choosability, Edge Choosability, and Total Choosability of Outerplane Graphs

✍ Wang Weifan; Ko-Wei Lih 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 101 KB

Let χ l (G), χ l (G), χ l (G), and (G) denote, respectively, the list chromatic number, the list chromatic index, the list total chromatic number, and the maximum degree of a non-trivial connected outerplane graph G. We prove the following results. ( 1 and only if G is an odd cycle. This proves the

Matrix Choosability

✍ Matt DeVos 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 149 KB

Let F be a finite field with p c elements, let A be a n\_n matrix over F, and let k be a positive integer. When is it true that for all X 1 , ..., Ax= y? It is trivial that A has this property for k= p c &1 if det(A){0. The permanent lemma of Noga Alon proves that if perm(A){0, then A has this prop