Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

De
116 pages
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
Voir plus Voir moins

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.

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).

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 systems, etc. Due to its wide range of applications to real-
life problems, and due to the development of computer sciences, graph theory has
developedrapidly in thepast century. One of the mainbranches of graph theoryis
graphcoloring,whichisthesubjectofstudyofthisthesis.
Definition1.1 Let G=(V;E) be a graph.
• Thedegree of a vertex of G is the number of edges incident to it.
7• The minimum degree of G is the minimum of the degree of its vertices. We
define similarly themaximumdegree of G.
• The summation of the degree of all vertices of G is equal to 2|E|. So the
2|E|
averagedegree of G is .
|V|
• ThemaximumaveragedegreeofGisthemaximum oftheaveragedegreeof
its subgraphs, where asubgraph is obtained by deleting edges and vertices.
Definition1.2 Let G=(V;E) be a graph. A path in G is a sequence v ;v ;:::;v1 2 n
of distinct vertices of G such that v is adjacent to v for any i =1;:::;n−1. Ifi i+1
moreover v is adjacent to v , then v ;v ;:::;v is called a cycle of length n.1 n 1 2 n
Definition1.3 A graph is planar if it can be drawn in the plane such that no two
vertices overlap, and edges intersect only at their end vertices.
Definition1.4 Let G=(V;E) be a graph.
• Given a positive integer k, and a set of k colors, a proper vertex k-coloring
ofGisanassignmentofoneofthek colorstoeachvertexofGsuchthatad-
jacentverticesarecoloredbydistinctcolors. SeeFigure1.1foranexample.
• ThechromaticnumberofG,denotedbyχ(G),istheminimumk forwhichG
has a proper vertex k-coloring.
1
2
3 2
2 1
3 1
2 3
Figure1.1: Apropervertex3-coloringofthePetersengraph.
Vertex coloring models to a number of scheduling problems. In the simplest
form, a given set of jobs needs to be assigned to time slots, each job requiring one
suchslot. Jobscanbescheduledinanyorder,butpairsofjobsmaybeinconflictin
8thesensethattheymaynotbeassignedtothesametimeslot,forexamplebecause
theybothrelyonasharedresource. Thecorrespondinggraphcontainsavertexfor
every job and an edge for every conflicting pair of jobs. The chromatic number of
the graph is exactly the minimum span, the optimal time to finish all jobs without
conflicts. Some other scheduling problems have different requirements. Vertex
coloring of graphs has many variations, which leads to different kinds of graph
colorings.
1.2 Circularcoloring
Definition1.5 Let G = (V;E) be a graph, and p;q be two positive integers with
p>2q.
• A (p;q)-coloring of G is a mapping c :V →{0;1;:::;p−1} such that for
any adjacent vertices x and y of G, q6|c(x)−c(y)|6 p−q.
• We say that G is(p;q)-colorable if G admits a (p;q)−coloring.
• The circular chromatic number χ (G) of G is the infimum of the ratios p=qc
for which G is (p;q)-colorable.
InChapter2,wegiveupperboundsonthecircularchromaticnumberoftriangle-
free graphs with bounded maximum average degree. Recall that the maximum av-
erage degree mad(G) of a graph G is the maximum of the average degree of its
subgraphs. Agraphistriangle-freeifitdoesnotcontainanycycleoflengththree.
Theorem1.1 LetGbeasimpletriangle-freegraphwithmaximumaveragedegree
mad(G).
• Ifmad(G)<22=9, thenχ (G)611=4;c
• Ifmad(G)<5=2, thenχ (G)614=5.c
1.3 Totalcoloring
In Chapter 3, we consider total coloring, (d;1)-total labeling and circular (d;1)-
totallabeling.
Definition1.6 Let G=(V;E) be a graph.
9• Atotalk-coloringofGisacoloringofV∪E usingk colorssuchthatnotwo
adjacent or incident elements get the same color.
• We say that G is total k-colorable if G admits a total k-coloring.
′′
• The total chromatic number of G, denoted byχ (G) is the smallest integer k
such that G has a total k-coloring.
InChapter3weprovethefollowing.
Theorem1.2 Let G be a planar graph with maximum degree 8. If for each vertex
v,thereisanintegerk ∈{3;4;5;6;7;8}suchthatGhasnok -cyclecontainingv,v v
then G is total 9-colorable.
Theorem1.3 Let G be a planar graph of maximum degree 6. If for each vertex v,
there exists an integer k ∈{3;4;5;6;7;8} such that G has no k -cycle containingv v
v, then G is total 8-colorable.
1.4 (d;1)-totallabeling
Definition1.7 Let G=(V;E) be a graph.
• A(d;1)-totallabeling of G is a mapping c:V∪E →N such that
1. no two adjacent vertices or two incident edges have the same label,
2. and for any edge uv,|c(u)−c(uv)|>d.
T
• The (d;1)-total number of G, denoted byλ (G), is the smallest integer k ford
which there is a (d;1)-total labeling of G using labels 0;1;:::;k.
Recallthatthemaximumaveragedegreemad(G)ofagraphGisthemaximum
of the average degree of its subgraphs. A graph is subcubic if it has
degreeatmost3. InChapter3weprovethefollowing.
7 TTheorem1.4 Let G be a subcubic graph. Ifmad(G)< , thenλ (G)65.23
Snarksarecubicgraphsthatarenot3-edgecolorable. Theyareknowntobethe
onlypossiblecounterexamplestomanyconjectures. Snarkshavebeenextensively
studiedforthatandotherreasons.
10

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin