1 |
List circular coloring of even cyclesYang, Chung-ying 27 June 2004 (has links)
Suppose G is a graph and p >= 2q are positive integers. A
color-list is a mapping L: V --> P(0, 1,...,p-1) which assigns to each vertex a set L(v) of
permissible colors. An L-(p, q)-coloring of G is a (p,
q)-coloring h of G such that for each vertex v,
h(v) in L(v). We say G is L-(p, q)-colorable if
such a coloring exists. A color-size-list is a mapping f: V -->{0, 1, 2,..., p}, which assigns to each vertex v a
non-negative integer f(v). We say G is f-(p, q)-colorable
if for every color-list L with |{L}(v)| = f(v), G is
L-(p, q)-colorable. For odd cycles C, Raspaud and Zhu
gave a sharp sufficient condition for a color-size-list f under
which C is f-(2k+1, k)-colorable. The corresponding
question for even cycles remained open. In this paper, we
consider list circular coloring of even cycles. For each even cycle C of length n and for each positive integer k, we
give a condition on f which is sufficient and sharp for C to
be f-(2k+1, k)-colorable.
|
2 |
Circular coloring and acyclic choosability of graphs / Coloration circulaire et coloration acyclique par listes de graphesRoussel, Nicolas 14 December 2009 (has links)
Dans cette thèse, nous nous intéressons à la coloration circulaire des graphes planaires. Des bornes supérieures ont été données pour des graphes avec degré maximum borné, avec girth, la longueur de son plus petit cycle, bornée, avec des cycles manquants, etc. Ici nous donnerons de nouvelles bornes pour les graphes avec degré moyen maximum borné. Nous étudions également la coloration totale et la coloration (d,1)-totale de plusieurs familles infinies de graphes. Nous décrivons le nouveau concept de coloration (d,1)-totale circulaire. Enfin, nous discutons les conditions nécessaires pour qu'un graphe planaire admette une coloration acyclique par listes de taille 4. / In this thesis, we study the circular coloring of planar graphs. Upper bounds have been given for graphs with bounded maximum degree, with bounded girth, that is the length of its smallest cycle, with missing cycles, and so on. It has also been studied for graphs with bounded maximum average degree. Here we give new upper bounds for that latter case. We also study the total coloring and ($d,1$)-total labeling of a few infinite families of graphs and describe the new concept of circular ($d,1$)-total labeling of graphs. In the last part, we will discuss conditions for a planar graph to be acyclically $4$-choosable.
|
3 |
Circular colorings and acyclic choosability of graphsRoussel, Nicolas 23 December 2009 (has links)
Abstract: This thesis studies five kinds of graph colorings: the circular coloring,
the total coloring, the (d; 1)-total labeling, the circular (r; 1)-total labeling, and the
acyclic list coloring.
We give upper bounds on the circular chromatic number of graphs with small
maximum average degree, mad for short. It is proved that if mad(G)<22=9 then G
has a 11=4-circular coloring, if mad(G) < 5=2 then G has a 14=5-circular coloring.
A conjecture by Behzad and Vizing implies that £G+2 colors are always sufficient
for a total coloring of graphs with maximum degree £G. The only open case for planar graphs is for £G = 6. Let G be a planar in which no vertex is contained in cycles of all lengths between 3 and 8. If £G(G) = 6, then G is total 8-colorable. If £G(G) = 8, then G is total 9-colorable.
Havet and Yu [23] conjectured that every subcubic graph G ̸=K4 has (2; 1)-total
number at most 5. We confirm the conjecture for graphs with maximum average
degree less than 7=3 and for flower snarks.
We introduce the circular (r; 1)-total labeling. As a relaxation of the aforementioned
conjecture, we conjecture that every subcubic graph has circular (2; 1)-total number at most 7. We confirm the conjecture for graphs with maximum average degree less than 5=2.
We prove that every planar graph with no cycles of lengths 4, 7 and 8 is acyclically
4-choosable. Combined with recent results, this implies that every planar
graph with no cycles of length 4;k; l with 5 6 k < l 6 8 is acyclically 4-choosable.
|
Page generated in 0.1047 seconds