Return to search

Circular colorings and acyclic choosability of graphs

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.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-1223109-135602
Date23 December 2009
CreatorsRoussel, Nicolas
ContributorsGerard Chang, Ko-Wei Lih, Tsai-Lien Wong, Hong-Gwa Yeh, Andr&#x00E9; Raspaud, Mickael Montassier, Li-Da Tong, Yeong-Nan Yeh, Xuding Zhu
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-1223109-135602
Rightsunrestricted, Copyright information available at source archive

Page generated in 0.002 seconds