Acyclic k choosability on planar graphs
75
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
75
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Title Acyclic k-choosability on planar graphs Min Chen and André Raspaud LaBRI, Université Bordeaux 1, France JGA, November 5-6, 2009 Min Chen and André Raspaud (LaBRI) Acyclic k-choosability on planar graphs November 6, 2009 1 / 52
Voir
- graph induced
- ?uv ?
- color classes
JGA, November 5-6, 2009
LaBRI, Université Bordeaux 1, France
2
Min Chen and André Raspaud
Acyclic k -choosability on planar graphs
195/
Our main theorem.
Definitions and some known results.
Conclusions and problems.
Outlines
290025/seniltuO
Definition: A proper k -coloring of the vertices of a graph G is a mapping π : V ( G ) → { 1 , ∙ ∙ ∙ , k } such that ∀ uv ∈ E ( G ) , π ( u ) 6 = π ( v ) .
5/200396r2,efiDtsDefinitownresuldnosemnkinitnoasngirolocreporPsnoi
Definition: A proper k -coloring of the vertices of a graph G is a mapping π : V ( G ) → { 1 , ∙ ∙ ∙ , k } such that ∀ uv ∈ E ( G ) , π ( u ) 6 = π ( v ) .
,20094/5vomeeb6rgrarhpNsnpyonalaabositilkcilohc-)IRBcycA
The acyclic chromatic number , denoted by χ a ( G ) , of a graph G , is the smallest integer k such that G has an acyclic k -coloring.
A proper vertex coloring of a graph is acyclic if the graph induced by the union of every two color classes is a forest .
A proper vertex coloring of a graph G is acyclic if there is no bicolored cycle in G .
095/52
The acyclic coloring of graphs was introduced by Grünbaum in 1973.
graranplontylibi02,6rebmevoNshpaaBRIud(LaspadréRooas-khclcciA)yc
A proper vertex coloring of a graph is acyclic if the graph induced by the union of every two color classes is a forest .
A proper vertex coloring of a graph G is acyclic if there is no bicolored cycle in G .
595/2
The acyclic chromatic number , denoted by χ a ( G ) , of a graph G , is the smallest integer k such that G has an acyclic k -coloring.
The acyclic coloring of graphs was introduced by Grünbaum in 1973.
eb6r2,00MhCniRB)I(daLilkccAcydAndenanspauréRaargranalmevoNshpabosho-cnpyoitilitinAsnolcycoccirilongeDnfitioisnnasdmoeknownresultsDefi
A proper vertex coloring of a graph G is acyclic if there is no bicolored cycle in G .
5/52
The acyclic coloring of graphs was introduced by Grünbaum in 1973.
The acyclic chromatic number , denoted by χ a ( G ) , of a graph G , is the smallest integer k such that G has an acyclic k -coloring.
A proper vertex coloring of a graph is acyclic if the graph induced by the union of every two color classes is a forest .
re,60290shoNevbm
