Coloration circulaire et coloration acyclique par listes de graphes, Circular coloring and acyclic choosability of graphs

Nicolas Roussel

Description

Sous la direction de André Raspaud, Xuding Zhu
Thèse soutenue le 14 décembre 2009: Bordeaux 1
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.
-Théorie des graphes
-Coloration circulaire
-Coloration acyclique par liste
-Graphes planaires
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.
-Graph theory
-Circular coloring
-Acyclic choosability
-Planar graph
Source: http://www.theses.fr/2009BOR13889/document

Sujets

• Théorie des graphes

Informations

• Publié par: Thesee
• Nombre de lectures: 63
• 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