La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | Thesee |
Nombre de lectures | 42 |
Langue | English |
Extrait
oN d’ordre: 3889
`THESE
´ ´ `PRESENTEE A
´L’UNIVERSITEBORDEAUXI
´ ´ECOLEDOCTORALEDEMATHEMATIQUESET
D’INFORMATIQUE
ParNicolasRoussel
POUROBTENIRLEGRADEDE
DOCTEUR
´ ´SPECIALITE:INFORMATIQUE
Colorationcirculaireetcolorationacycliqueparlistesdegraphes
Soutenuele: 14Decembre´ 2009
Apres` avisdesrapporteurs:
ArnaudPecherˆ .... Professeur
Hong-GwaYeh ... Professeur
Devantlacommissiond’examencomposee´ de:
MickaelMontassier MaˆıtredeConferences´ .......... Examinateur
Andre´ Raspaud .... Professeur,Directeurderecherche
Hong-GwaYeh ... ..................... President´
XudingZhu ....... Professeur,Directeurderecherche Examinateur
2009Thanks
ThankstomyadvisorsProf. Andre´ RaspaudandProf. XudingZhu.
ˆThanks to the thesis reviewers Prof. Arnaud Pecher, Prof. Hong-Gwa Yeh and
Prof. MickaelMontassier.
Thanks to the defense committee members for their valuable comments and re-
marks: Prof. Gerard J. Chang, Prof. Ko-Wei Lih, Prof. Mickael Montassier, Prof.
Andre´ Raspaud, Prof. Li-Da Tong, Prof. Tsai-Lian Wang, Prof. Hong-Gwa Yeh,
Prof. Yeong-NanYeh,Prof. XudingZhu.
Thanks to all those who shared ideas with me and accepted to work with me, in-
cluding Dr. David Cariolaro, Prof. Gerard J. Chang, Min Chen, Prof. Daniel
Gonc¸alves, Dr. Louis Esperet, Prof. Mickael Montassier, Prof. Jaroslav Nesetril,
Dr. Zhi-Shi Pan, Prof. Arnaud Pecher, Prof. Andre´ Raspaud, Prof. Moshe Rosen-
feld, Prof. Siegfried Schaible, Prof. Claude Tardiff, Prof. Li-Da Tong, Prof. Tsai-
LianWang,Prof. XudingZhu.
Thanks to all faculty members, staff members and students of National Sun Yat-
SenUniversityandUniversite´ Bordeaux1fortheirpatience,helpandsupport.
Thanks to all organizers and participants of the numerous conferences featuring
GraphTheorythatIattendedbetween2005and2009.
ThanksforthesupportreceivedfromTaiwanGovernment,fromNationalSunYat-
Sen University, the National Science Council of Taiwan, Prof. Xuding Zhu, and
from Universite´ Bordeaux 1, Laboratoire Bordelais de Recherche en Informatique
(LaBRI),Prof. Andre´ Raspaud,programme egide´ andCNRS.
Thankstoallthefriends,tomyfamily,andtoallthoseImetduringthepreparation
ofmyPhDthesisandallothersIdidnotmentionbyname.
2̸
Colorationcirculaireetcolorationacycliqueparlistesdegraphes
Resum´ e:´ Cette these` s’interesse´ a` cinq types de colorations de graphes, la col-
orationcirculaire,lacolorationtotale,lacoloration(d;1)-totale,lacoloration(r;1)-
totaleainsiquelacolorationacycliqueparlistes.
Pour les graphes sans triangle de degre´ moyen maximum dmm(G) borne,´ nous
prouvonsquesidmm(G)<22=9,alorsGaunecoloration11=4-circulaire. Egale-
ment,sidmm(G)<5=2,alors G aunecoloration14=5-circulaire.
Une conjecture de Behzad et Vizing implique que∆+2 couleurs sont toujours
suffisantes pour une coloration totale des graphes de degre´ maximum ∆. Pour les
graphes planaires, le seul cas ouvert est pour∆=6. Soit G un graphe planaire tel
qu’aucun sommet ne soit contenu dans des cycles de toutes les longueurs entre 4
et 8. Si ∆(G) =6 , alors G a une coloration totale avec 8 couleurs. Si ∆(G) =8,
alors G aunecolorationtotaleavec9couleurs.
Havet et Yu conjecturent que tout graphe sous-cubique G = K a un nombre4
(d;1)-total au plus 5. Nous confirmons la conjecture pour les graphes de degre´
moyenmaximummoinsde7=3etpourles flower snarks.
Nous introduisons le concept de coloration (r;1)-totale circulaire. Une relax-
ationdelaprec´ edente´ conjecture,nousconjecturonsquetoutgraphesous-cubique
a un nombre (2;1)-total circulaire au plus 7. Nous confirmons la conjecture pour
lesgraphesdedegre´ moyenmaximummoinsde5=2.
Nous prouvons que tout graphe planaire sans cycles de taille 4, 7 et 8 a une
coloration acyclique par listes de taille 4. Combine´ avec d’autre resultats´ recents,´
celaimpliquequetoutgrapheplanairesanscyclesdetaille4;k;l,avec56k<l68
aunecolorationacycliqueparlistesdetaille4.
Discipline: Informatique,Mathematiques´ appliquees´
Mots-clefs: Coloration circulaire, coloration totale, coloration (d;1)-totale, col-
oration (r;1)-totale circulaire, coloration acyclique par listes, graphes planaires,
degre´ moyenmaximum,interdictionsdecycles
LaBRI,
Universite´ Bordeaux1,
351coursdelaLiberation,´
33405TalenceCedex(FRANCE).
3̸
Circularcoloringandacyclicchoosabilityofgraphs
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
acycliclistcoloring.
Wegiveupperboundsonthecircularchromaticnumberoftriangle-freegraphs
with bounded maximum average degree mad(G). 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-
circularcoloring.
A conjecture by Behzad and Vizing implies that ∆+2 colors are always suffi-
cient for a total coloring of graphs with maximum degree ∆. The only open case
forplanargraphsisfor∆=6. LetGbeaplanarinwhichnovertexiscontainedin
cycles of all lengths between 3 and 8. If ∆(G)=6, then G is total 8-colorable. If
∆(G)=8,then G istotal9-colorable.
Havet and Yu conjectured that every subcubic graph G = K has (2;1)-total4
number at most 5. We confirm the conjecture for graphs with maximum average
degreelessthan7=3andfor flower snarks.
We introduce the circular (r;1)-total labeling. As a relaxation of the aforemen-
tioned 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
degreelessthan5=2.
Weprovethat everyplanar graph with no cyclesof lengths 4, 7 and 8 isacycli-
cally 4-choosable. Combined with recent results, this implies that every planar
graphwithnocyclesoflength4;k;l with56k<l68isacyclically4-choosable.
Discipline: Computerscience,Appliedmathematics
Keywords: Circular coloring, total coloring, (d;1)-total labeling, circular (r;1)-
total labeling, acyclic choosability, planar graphs, maximum average degree, for-
biddencycles
LaBRI,
Universite´ Bordeaux1,
351coursdelaLiberation,´
33405TalenceCedex(FRANCE).
4Contents
1 Introduction 7
1.1 Basicdefinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Circularcoloring . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Totalcoloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 (d;1)-totallabeling . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Circular(r;1)-totallabeling . . . . . . . . . . . . . . . . . . . . . 11
1.6 Acyclicchoosability . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Circularcoloring 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Maintools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Graphswithmaximumaveragedegreelessthan22=9 . . . . . . . 21
2.4withaveragedegreelessthan5=2 . . . . . . . . 25
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3 Totalcoloring,(d;1)-totallabelingandcircular(r;1)-totallabeling 50
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2 Totalcoloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.1 Planargraphswith∆(G)=6 . . . . . . . . . . . . . . . . 56
3.2.2with∆(G)=8 . . . . . . . . . . . . . . . . 68
3.3 (d;1)-totallabeling . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.3.1 Graphswithmad(G)<7=3 . . . . . . . . . . . . . . . . 75
3.3.2 Flowersnarks . . . . . . . . . . . . . . . . . . . . . . . . 79
3.4 Circular (r;1)-totallabelingofgraphswithmad(G)<5=2 . . . . 80
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4 Acyclicchoosability 87
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.2 Planargraphswithno4;7and8-cycles . . . . . . . . . . . . . . . 88
54.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5 Conclusion 108
5.1 Circularcoloring . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.2 Totalcoloring,(d;1)-totallabelingandcircular(r;1)-totallabeling 109
5.3 Acyclicchoosability . . . . . . . . . . . . . . . . . . . . . . . . 110
6Chapter1
Introduction
This thesis deals mainly with graph coloring problems, which are in the core of
graph theory. The basic definitions needed for a good understanding of the docu-
mentwillbegiveninthefirstsection. Wewillintroducegraphsandtheircolorings,
especially the five main colorings discussed in this thesis, that is circular color-
ing, total coloring, (d;1)-total labeling, circular (d;1)-total labeling, and acyclic
choosability.
1.1 Basicdefinitions
A graph consists of a vertex set V and an edge set E, where each edge is a 2-
elementsubsetofV. WewriteG=(V;E)toindicateagraphnamedGwithvertex
setV and edge set E. If e={u;v}∈E, then we say u and v are adjacent, and the
edge e is incident to u and v. Two distinct edges incident to a common vertex are
said to be to each other. We will consider only simple graphs, that is with
noloopandwithatmostoneedgebetweenanytwovertices.
Graphs are used as models for many real-life systems, such as electrical net-
works, transportation