Graph Theory » Coloring » Homomorphisms

Circular choosability of planar graphs ★

Author(s): Mohar

Let $ G = (V, E) $ be a graph. If $ p $ and $ q $ are two integers, a $ (p,q) $-colouring of $ G $ is a function $ c $ from $ V $ to $ \{0,\dots,p-1\} $ such that $ q \le |c(u)-c(v)| \le p-q $ for each edge $ uv\in E $. Given a list assignment $ L $ of $ G $, i.e.~a mapping that assigns to every vertex $ v $ a set of non-negative integers, an $ L $-colouring of $ G $ is a mapping $ c : V \to N $ such that $ c(v)\in L(v) $ for every $ v\in V $. A list assignment $ L $ is a $ t $-$ (p,q) $-list-assignment if $ L(v) \subseteq \{0,\dots,p-1\} $ and $ |L(v)| \ge tq $ for each vertex $ v \in V $ . Given such a list assignment $ L $, the graph G is $ (p,q) $-$ L $-colourable if there exists a $ (p,q) $-$ L $-colouring $ c $, i.e. $ c $ is both a $ (p,q) $-colouring and an $ L $-colouring. For any real number $ t \ge 1 $, the graph $ G $ is $ t $-$ (p,q) $-choosable if it is $ (p,q) $-$ L $-colourable for every $ t $-$ (p,q) $-list-assignment $ L $. Last, $ G $ is circularly $ t $-choosable if it is $ t $-$ (p,q) $-choosable for any $ p $, $ q $. The circular choosability (or circular list chromatic number or circular choice number) of G is $$cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$$

Problem   What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

Posted by rosskang
updated August 23rd, 2012
add new comment
Topology

A conjecture about direct product of funcoids ★★

Author(s): Porton

Conjecture   Let $ f_1 $ and $ f_2 $ are monovalued, entirely defined funcoids with $ \operatorname{Src}f_1=\operatorname{Src}f_2=A $. Then there exists a pointfree funcoid $ f_1 \times^{\left( D \right)} f_2 $ such that (for every filter $ x $ on $ A $) $$\left\langle f_1 \times^{\left( D \right)} f_2 \right\rangle x = \bigcup \left\{ \langle f_1\rangle X \times^{\mathsf{FCD}} \langle f_2\rangle X \hspace{1em} | \hspace{1em} X \in \mathrm{atoms}^{\mathfrak{A}} x \right\}.$$ (The join operation is taken on the lattice of filters with reversed order.)

A positive solution of this problem may open a way to prove that some funcoids-related categories are cartesian closed.

Keywords: category theory; general topology

Posted by porton
updated July 26th, 2012
add new comment
Number Theory

Special M ★★

Author(s): Kimberling

Let $ r $ denote the golden ratio, $ \frac{(1+\sqrt{5})}{2} $ and let $ \lfloor \rfloor $ denote the floor function. For fixed $ n $, let $ u(k) = \lfloor kr^n \rfloor $, let $ v(k) = \lfloor kr \rfloor^n $, and let $ w(k) = \left \lfloor \frac{v(k)}{k^{(n-1)}} \right \rfloor $. We can expect $ w $ to have about the same growth rate as $ u $.

Conjecture   Prove or disprove that for every fixed $ n > 0 $, as $ k $ ranges through all the positive integers, there is a number $ M $ such that $ u(k) - w(k) $ takes each of the values $ 1,2,\dots,M $ infinitely many times, and $ u(k) - w(k) \leq M $. (Can you formulate $ M $ as a function of $ n $? Generalize for other numbers $ r $?)

Keywords:

Posted by vprusso
updated June 12th, 2012
add new comment