Site.VertexPartition History

Hide minor edits - Show changes to markup

June 15, 2016, at 01:59 PM by 193.49.104.233 -
Changed line 46 from:
 (I,F5)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
to:
 (I,F5)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. http://arxiv.org/pdf/1606.04394v1.pdf
Changed line 50 from:
 (I,F3)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
to:
 (I,F3)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. http://arxiv.org/pdf/1606.04394v1.pdf
Changed line 53 from:
 (I,F2)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
to:
 (I,F2)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. http://arxiv.org/pdf/1606.04394v1.pdf
June 15, 2016, at 01:57 PM by 193.49.104.233 -
Changed line 46 from:
 (I,F5)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
to:
 (I,F5)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
Changed line 50 from:
 (I,F3)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
to:
 (I,F3)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
Changed line 53 from:
 (I,F2)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
to:
 (I,F2)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
June 15, 2016, at 01:53 PM by 193.49.104.233 -
Added line 46:
 (I,F5)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
Added line 50:
 (I,F3)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
Added line 53:
 (I,F2)F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree.
January 11, 2016, at 10:39 AM by 193.49.104.233 -
Changed lines 33-34 from:
 (F,F5)François Dross, Mickael Montassier, Alexandre Pinlou. Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. http://arxiv.org/abs/1601.01523, 2016.
to:
 (F,F5)François Dross, Mickael Montassier, Alexandre Pinlou. Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. http://arxiv.org/pdf/1601.01523v1.pdf
January 11, 2016, at 10:38 AM by 193.49.104.233 -
Added lines 33-34:
 (F,F5)François Dross, Mickael Montassier, Alexandre Pinlou. Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. http://arxiv.org/abs/1601.01523, 2016.
December 02, 2015, at 02:45 PM by 193.49.104.233 -
Changed line 35 from:
 (D1,D10)H. Choi, I. Choi, J. Jeong, G. Suh. (1,k)-coloring of graphs with girth at least 5 on a surface. arXiv:1412.0344, 2014.
to:
 (D1,D10)H. Choi, I. Choi, J. Jeong, G. Suh. (1,k)-coloring of graphs with girth at least 5 on a surface. http://arxiv.org/pdf/1412.0344v1.pdf
Changed line 43 from:
 (O12,O12)L. Esperet and P. Ochem.Islands in graphs on surfaces. http://arxiv.org/pdf/1402.2475v3.pdf
to:
 (O12,O12)L. Esperet and P. Ochem. Islands in graphs on surfaces. http://arxiv.org/pdf/1402.2475v3.pdf
December 02, 2015, at 02:43 PM by 193.49.104.233 -
Changed lines 13-14 from:
  • dk the class of k-degenerate graphs
to:
  • dk the class of k-degenerate graphs,
  • Ok the class of graphs of order k.
Added line 43:
 (O12,O12)L. Esperet and P. Ochem.Islands in graphs on surfaces. http://arxiv.org/pdf/1402.2475v3.pdf
December 02, 2015, at 08:45 AM by 193.49.104.233 -
Changed line 55 from:

Thanks to Ilkyoo Choi, Pascal Ochem.

to:

Thanks to Ilkyoo Choi, François, Dross, Pascal Ochem.

December 02, 2015, at 08:37 AM by 193.49.104.233 -
Changed line 41 from:
 (P14,P14)M. Axenovich, T. Ueckerdt, and P. Weiner. Splitting planar graphs of girth 6 into two linear forests with short paths. http://arxiv.org/pdf/1507.02815.pdf
to:
 (P14,P14)M. Axenovich, T. Ueckerdt, and P. Weiner. Splitting planar graphs of girth 6 into two linear forests with short paths. http://arxiv.org/pdf/1507.02815.pdf
Changed line 55 from:

Thanks to Pascal Ochem.

to:

Thanks to Ilkyoo Choi, Pascal Ochem.

December 02, 2015, at 08:36 AM by 193.49.104.233 -
Changed lines 41-42 from:
 (P14,P14)M. Axenovich, T. Ueckerdt, and P. Weiner. '''Splitting planar graphs of girth 6 into two linear

forests with short paths'''. http://arxiv.org/pdf/1507.02815.pdf

to:
 (P14,P14)M. Axenovich, T. Ueckerdt, and P. Weiner. Splitting planar graphs of girth 6 into two linear forests with short paths. http://arxiv.org/pdf/1507.02815.pdf
December 02, 2015, at 08:36 AM by 193.49.104.233 -
Added lines 8-9:
  • P the class of paths,
  • Pk the class of paths ol length at most k,
Added lines 41-42:
 (P14,P14)M. Axenovich, T. Ueckerdt, and P. Weiner. '''Splitting planar graphs of girth 6 into two linear

forests with short paths'''. http://arxiv.org/pdf/1507.02815.pdf

July 28, 2015, at 01:38 PM by 193.49.104.233 -
Changed line 52 from:

Thank you to Pascal Ochem.

to:

Thanks to Pascal Ochem.

June 12, 2015, at 01:53 PM by 193.49.104.233 -
Changed line 52 from:

Thank you to Pascal Ochem

to:

Thank you to Pascal Ochem.

June 12, 2015, at 01:52 PM by 193.49.104.233 -
Changed line 48 from:

.

to:
June 12, 2015, at 01:52 PM by 193.49.104.233 -
Changed line 50 from:

Acknowledgement

to:

Acknowledgements

June 12, 2015, at 01:51 PM by 193.49.104.233 -
Changed line 50 from:

Acknowledgment

to:

Acknowledgement

June 12, 2015, at 01:51 PM by 193.49.104.233 -
Added lines 49-53:

Acknowledgment

Thank you to Pascal Ochem

June 12, 2015, at 01:44 PM by 193.49.104.233 -
Deleted line 39:
 (S2,S2)O.V. Borodin and A.O. Ivanova. List strong linear 2-arboricity of sparse graphs. Journal of Graph Theory, 67(2):83-90, 2011.
Changed line 41 from:
 (I,D2)M. Montassier and P. Ochem. Near-colorings: non-colorable graphs and NP-completness. http://arxiv.org/abs/1306.0752
to:
 (I,D2)M. Montassier and P. Ochem. Near-colorings: non-colorable graphs and NP-completness. Electronic Journal of Combinatorics,Volume 22, Issue 1, 2015.
June 10, 2015, at 06:07 PM by 193.49.104.233 -
Changed line 45 from:
10(I,D1) ?Open question.
to:
10(I,D1) ?Open question.
June 10, 2015, at 06:06 PM by 193.49.104.233 -
Added line 45:
10(I,D1) ?Open question.
June 10, 2015, at 06:05 PM by 193.49.104.233 -
Changed line 37 from:
 (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
to:
 (I,Dk) for any kO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
June 10, 2015, at 06:02 PM by 193.49.104.233 -
Changed line 13 from:

Observe that: d1=F, D0=I, D1=S1

to:

Observe that: d1=F, D0=I, D1=S1=F1

June 10, 2015, at 06:01 PM by 193.49.104.233 -
Added line 44:
9(I,D1)L. Esperet, M. Montassier, P. Ochem, and A. Pinlou. A complexity dichotomy for the coloring of sparse graphs. Journal of Graph Theory, 73(1):85-102, 2013.
June 10, 2015, at 05:57 PM by 193.49.104.233 -
Added line 42:
 (I,D2)M. Montassier and P. Ochem. Near-colorings: non-colorable graphs and NP-completness. http://arxiv.org/abs/1306.0752
June 10, 2015, at 05:41 PM by 193.49.104.233 -
Changed line 37 from:
 no (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
to:
 (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
June 10, 2015, at 05:41 PM by 193.49.104.233 -
Changed line 37 from:
 no (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
to:
 no (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
June 10, 2015, at 05:40 PM by 193.49.104.233 -
Changed line 37 from:
 no (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
to:
 no (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
June 10, 2015, at 05:39 PM by 193.49.104.233 -
Changed line 37 from:
no (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
to:
 no (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
June 10, 2015, at 05:39 PM by 193.49.104.233 -
Changed line 37 from:
(I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
to:
no (I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
June 10, 2015, at 05:38 PM by 193.49.104.233 -
Added line 37:
(I,Fd) for any dO.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010.
June 09, 2015, at 09:39 PM by 193.49.104.233 -
Added lines 14-16:

Consider i classes of graphs G1, . . . , Gi. A (G1, . . . , Gi)-partition of a graph G is a vertex-partition into i sets V1,...,Vi such that, for all 1 <= j <= i, the graph G[Vj] induced by Vj belongs to Gj. For example, a (I,F,d2)-partition is a vertex-partition into three sets V1,V2,V3 such that G[V1] is an empty graph, G[V2] is a forest, and G[V3] is a 2-degenerate graph.

June 09, 2015, at 09:36 PM by 193.49.104.233 -
Added lines 14-15:

Results

June 09, 2015, at 09:35 PM by 193.49.104.233 -
Changed line 40 from:
to:

.

June 09, 2015, at 09:35 PM by 193.49.104.233 -
Changed line 40 from:

comment .

to:
June 09, 2015, at 09:35 PM by 193.49.104.233 -
Changed line 40 from:

.

to:

comment .

June 09, 2015, at 09:33 PM by 193.49.104.233 -
Changed line 40 from:

.

to:

.

June 09, 2015, at 05:04 PM by 193.49.104.233 -
Changed lines 38-39 from:
to:

.

June 09, 2015, at 05:03 PM by 193.49.104.233 -
Changed lines 38-39 from:

to:
June 09, 2015, at 05:03 PM by 193.49.104.233 -
Changed line 39 from:

to:

June 09, 2015, at 05:02 PM by 193.49.104.233 -
Changed line 39 from:

coucou

to:

June 09, 2015, at 05:02 PM by 193.49.104.233 -
Changed lines 39-40 from:
to:

coucou


June 09, 2015, at 05:02 PM by 193.49.104.233 -
Changed lines 39-40 from:

to:
June 09, 2015, at 05:01 PM by 193.49.104.233 -
Added lines 38-39:
June 09, 2015, at 05:01 PM by 193.49.104.233 -
Deleted line 37:
Deleted line 38:
June 09, 2015, at 05:00 PM by 193.49.104.233 -
Added line 40:
June 09, 2015, at 05:00 PM by 193.49.104.233 -
Added line 39:

June 09, 2015, at 05:00 PM by 193.49.104.233 -
Added lines 38-39:

Keywords: graph theory, graphs, partition, vertex, planar graphs, given girth

June 09, 2015, at 04:59 PM by 193.49.104.233 -
Changed line 34 from:
 (S2,S2)O.V. Borodin and A.O. Ivanova. List strong linear 2-arboricity of sparse graphs. Journal of Graph Theory, 67(2):83-90, 2011.
to:
 (S2,S2)O.V. Borodin and A.O. Ivanova. List strong linear 2-arboricity of sparse graphs. Journal of Graph Theory, 67(2):83-90, 2011.
June 09, 2015, at 04:58 PM by 193.49.104.233 -
Added lines 12-13:

Observe that: d1=F, D0=I, D1=S1

June 09, 2015, at 04:56 PM by 193.49.104.233 -
Changed line 33 from:
 (D1,D1)O.V. Borodin, A. Kostochka, M. Yancey. On 11-improper 22-coloring of sparse graphs. Discrete Mathematics, 313(22):2638-2649, 2013.
to:
 (D1,D1)O.V. Borodin, A. Kostochka, M. Yancey. On 1-improper 2-coloring of sparse graphs. Discrete Mathematics, 313(22):2638-2649, 2013.
June 09, 2015, at 04:56 PM by 193.49.104.233 -
Added line 33:
 (D1,D1)O.V. Borodin, A. Kostochka, M. Yancey. On 11-improper 22-coloring of sparse graphs. Discrete Mathematics, 313(22):2638-2649, 2013.
Deleted line 34:
 (D1,D1)F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006.
June 09, 2015, at 11:18 AM by 193.49.104.233 -
June 09, 2015, at 11:14 AM by 193.49.104.233 -
Changed lines 35-36 from:
9 
10 
to:
11(I,D1)J. Kim, A. Kostochka, X. Zhu.Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs. European Journal of Combinatorics, 42:26-48, 2014.
June 09, 2015, at 11:09 AM by 193.49.104.233 -
Added lines 8-9:
  • S the class of star forests,
  • Sk the class of star forests with maximum degree at most k,
Changed lines 31-32 from:
7 
8 
to:
7(I,D4)O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014.
 (S2,S2)O.V. Borodin and A.O. Ivanova. List strong linear 2-arboricity of sparse graphs. Journal of Graph Theory, 67(2):83-90, 2011.
8(I,D2)O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014.
 (D1,D1)F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006.
June 09, 2015, at 11:02 AM by 193.49.104.233 -
Changed lines 28-32 from:
 (D2,D2)F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006.
to:
 (D2,D2)F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006.
7 
8 
9 
10 
June 09, 2015, at 11:01 AM by 193.49.104.233 -
Changed line 23 from:
 (D1,D10)H. Choi, I. Choi, J. Jeong, G. Suh.(1,k)-coloring of graphs with girth at least 5 on a surface. arXiv:1412.0344, 2014.
to:
 (D1,D10)H. Choi, I. Choi, J. Jeong, G. Suh. (1,k)-coloring of graphs with girth at least 5 on a surface. arXiv:1412.0344, 2014.
Added lines 27-28:
6(D1,D4)O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014.
 (D2,D2)F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006.
June 09, 2015, at 10:59 AM by 193.49.104.233 -
Changed lines 23-24 from:
 (D1,D10)H. Choi, I. Choi, J. Jeong, G. Suh.'''(1,k)-coloring of graphs with girth at least 5 on a surface

'''. arXiv:1412.0344, 2014.

to:
 (D1,D10)H. Choi, I. Choi, J. Jeong, G. Suh.(1,k)-coloring of graphs with girth at least 5 on a surface. arXiv:1412.0344, 2014.
June 09, 2015, at 10:59 AM by 193.49.104.233 -
Changed line 23 from:
 (D1,D10).'''(1,k)-coloring of graphs with girth at least 5 on a surface
to:
 (D1,D10)H. Choi, I. Choi, J. Jeong, G. Suh.'''(1,k)-coloring of graphs with girth at least 5 on a surface
Changed line 26 from:
 (D3,D5)I. Choi and A. Raspaud. Planar graphs with girth at least 5 are (3,5)-colorable. Discrete Mathematics, 318(4):661–667, 2015.
to:
 (D3,D5)I. Choi and A. Raspaud. Planar graphs with girth at least 5 are (3,5)-colorable. Discrete Mathematics, 318(4):661–667, 2015.
June 09, 2015, at 10:58 AM by 193.49.104.233 -
Changed lines 23-24 from:
 (D1,D10)
to:
 (D1,D10).'''(1,k)-coloring of graphs with girth at least 5 on a surface

'''. arXiv:1412.0344, 2014.

Changed line 26 from:
 (D3,D5)
to:
 (D3,D5)I. Choi and A. Raspaud. Planar graphs with girth at least 5 are (3,5)-colorable. Discrete Mathematics, 318(4):661–667, 2015.
June 09, 2015, at 10:46 AM by 193.49.104.233 -
Changed line 26 from:
 (D4,D4)F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree, Journal of Graph Theory 52(3):181-199, 2006.
to:
 (D4,D4)F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006.
June 09, 2015, at 10:46 AM by 193.49.104.233 -
Changed line 26 from:
 (D4,D4)
to:
 (D4,D4)F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree, Journal of Graph Theory 52(3):181-199, 2006.
June 09, 2015, at 10:42 AM by 193.49.104.233 -
Changed line 24 from:
 (D2,D6)O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory Series B, 104:72-80, 2014.
to:
 (D2,D6)O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014.
June 09, 2015, at 10:42 AM by 193.49.104.233 -
Changed lines 21-26 from:
 (I,d2)Folklore
to:
 (I,d2)Folklore
5(I,F)O.V. Borodin, A.N. Glebov. On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph (russian). Diskretnyi Analiz i Issledovanie Operatsii, 8(4):34–53, 2001.
 (D1,D10)
 (D2,D6)O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory Series B, 104:72-80, 2014.
 (D3,D5)
 (D4,D4)
June 09, 2015, at 10:37 AM by 193.49.104.233 -
Changed lines 20-21 from:
 (F,F)Folklore
 (I,d2)Folklore
to:
 (F,F)Folklore
 (I,d2)Folklore
June 09, 2015, at 10:36 AM by 193.49.104.233 -
Changed lines 19-21 from:
4(I,I,I)H. Grötzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8: 109–120, 1959.
to:
4(I,I,I)H. Grötzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8: 109–120, 1959.
 (F,F)Folklore
 (I,d2)Folklore
June 09, 2015, at 10:35 AM by 193.49.104.233 -
Changed line 19 from:
4 
to:
4(I,I,I)H. Grötzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8: 109–120, 1959.
June 09, 2015, at 10:33 AM by 193.49.104.233 -
Changed lines 13-18 from:
3(I,I,I,I)Appel K., Haken W. Every Planar Map is Four Colorable Part I. Discharging, Illinois Journal of Mathematics 21: 429–490, 1977.
  Appel K., Haken W., Koch J. Every Planar Map is Four Colorable Part II. Reducibility, Illinois Journal of Mathematics 21: 491–567, 1977.
 (I,F,F)
 (F2,F2,F2)
 (F,d2)
 (I,d3)
to:
3(I,I,I,I)K. Appel K, W. Haken. Every Planar Map is Four Colorable Part I. Discharging, Illinois Journal of Mathematics 21: 429–490, 1977.
  K. Appel, W. Haken W, J. Koch. Every Planar Map is Four Colorable Part II. Reducibility, Illinois Journal of Mathematics 21: 491–567, 1977.
 (I,F,F)O.V. Borodin. A proof of Grünbaum’s conjecture on the acyclic 5-colorability of planar graphs (russian). Dokl. Akad. Nauk SSSR, 231(1):18–20, 1976.
 (F2,F2,F2)K.S. Poh. On the linear vertex-arboricity of a plane graph. Journal of Graph Theory, 14(1):73–75, 1990.
 (F,d2)C. Thomassen. Decomposing a planar graph into degenerate graphs. Journal of Combinatorial Theory, Series B, 65(2):305–314, 1995.
 (I,d3)C. Thomassen. Decomposing a planar graph into an independent set and a 3-degenerate graph. Journal of Combinatorial Theory, Series B, 83(2):262–271, 2001.
June 09, 2015, at 10:28 AM by 193.49.104.233 -
Changed line 16 from:
 (F2,F2,F,2)
to:
 (F2,F2,F2)
Changed lines 18-19 from:
 (I,d3)
to:
 (I,d3)
4 
June 09, 2015, at 10:28 AM by 193.49.104.233 -
Changed lines 14-18 from:
  Appel K., Haken W., Koch J. Every Planar Map is Four Colorable Part II. Reducibility, Illinois Journal of Mathematics 21: 491–567, 1977.
to:
  Appel K., Haken W., Koch J. Every Planar Map is Four Colorable Part II. Reducibility, Illinois Journal of Mathematics 21: 491–567, 1977.
 (I,F,F)
 (F2,F2,F,2)
 (F,d2)
 (I,d3)
June 09, 2015, at 10:26 AM by 193.49.104.233 -
Changed line 13 from:
3(I,I,I,I)Appel K., Haken W. Every Planar Map is Four Colorable Part I. Discharging, Illinois Journal of Mathematics 21: 429–490, 1977.
to:
3(I,I,I,I)Appel K., Haken W. Every Planar Map is Four Colorable Part I. Discharging, Illinois Journal of Mathematics 21: 429–490, 1977.
June 09, 2015, at 10:26 AM by 193.49.104.233 -
Changed lines 13-14 from:
3(I,I,I,I)Appel K., Haken W. '''Every Planar Map is Four Colorable Part I. Discharging"', Illinois Journal of Mathematics 21: 429–490, 1977.
  Appel K., Haken W., Koch J. "'Every Planar Map is Four Colorable Part II. Reducibility"', Illinois Journal of Mathematics 21: 491–567, 1977.
to:
3(I,I,I,I)Appel K., Haken W. Every Planar Map is Four Colorable Part I. Discharging, Illinois Journal of Mathematics 21: 429–490, 1977.
  Appel K., Haken W., Koch J. Every Planar Map is Four Colorable Part II. Reducibility, Illinois Journal of Mathematics 21: 491–567, 1977.
June 09, 2015, at 10:25 AM by 193.49.104.233 -
Changed lines 13-14 from:
3(I,I,I,I)Appel K., Haken W. "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429–490, 1977.
  Appel K., Haken W., Koch J., "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567, 1977.
to:
3(I,I,I,I)Appel K., Haken W. '''Every Planar Map is Four Colorable Part I. Discharging"', Illinois Journal of Mathematics 21: 429–490, 1977.
  Appel K., Haken W., Koch J. "'Every Planar Map is Four Colorable Part II. Reducibility"', Illinois Journal of Mathematics 21: 491–567, 1977.
June 09, 2015, at 10:25 AM by 193.49.104.233 -
Changed lines 13-14 from:
3(I,I,I,I)Appel K., Haken W. "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429–490, 1977. \\ Appel K., Haken W., Koch J., "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567, 1977.
to:
3(I,I,I,I)Appel K., Haken W. "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429–490, 1977.
  Appel K., Haken W., Koch J., "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567, 1977.
June 09, 2015, at 10:24 AM by 193.49.104.233 -
Changed line 13 from:
3(I,I,I,I)Appel K., Haken W. "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429–490, 1977. Appel K., Haken W., Koch J., "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567, 1977.
to:
3(I,I,I,I)Appel K., Haken W. "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429–490, 1977. \\ Appel K., Haken W., Koch J., "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567, 1977.
June 09, 2015, at 10:24 AM by 193.49.104.233 -
Changed line 11 from:
to:
Changed line 13 from:
3(I,I,I,I)Appel
to:
3(I,I,I,I)Appel K., Haken W. "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429–490, 1977. Appel K., Haken W., Koch J., "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567, 1977.
June 09, 2015, at 10:21 AM by 193.49.104.233 -
Changed lines 11-12 from:
GirthVertex-partitionsReferences
to:
GirthVertex-partitionsReferences
June 09, 2015, at 10:20 AM by 193.49.104.233 -
Changed line 12 from:
GirthVertex-partitionsReferences
to:
GirthVertex-partitionsReferences
June 09, 2015, at 10:20 AM by 193.49.104.233 -
Changed lines 11-24 from:

(:table border=0 width=100%:) (:cell:)

 Girth

(:cell:)

 Vertex-partitions

(:cell:)

 References

(:cellnr:) 3 (:cell:) (I,I,I,I) (:cell:) Appel, (:tableend:)

to:
GirthVertex-partitionsReferences
3(I,I,I,I)Appel
June 09, 2015, at 10:18 AM by 193.49.104.233 -
Changed line 11 from:

(:table border=1 width=100%:)

to:

(:table border=0 width=100%:)

June 09, 2015, at 10:17 AM by 193.49.104.233 -
Changed line 19 from:
to:

3

Changed line 21 from:
to:

(I,I,I,I)

Changed line 23 from:
to:

Appel,

June 09, 2015, at 10:16 AM by 193.49.104.233 -
Changed line 13 from:

Girth

to:
 Girth
Changed line 15 from:

Vertex-partition

to:
 Vertex-partitions
Changed line 17 from:

Reference

to:
 References
June 09, 2015, at 10:16 AM by 193.49.104.233 -
Changed line 13 from:
to:

Girth

Changed line 15 from:
to:

Vertex-partition

Changed line 17 from:
to:

Reference

June 09, 2015, at 10:15 AM by 193.49.104.233 -
Changed lines 9-24 from:
  • dk the class of k-degenerate graphs
to:
  • dk the class of k-degenerate graphs

(:table border=1 width=100%:) (:cell:)

(:cell:)

(:cell:)

(:cellnr:)

(:cell:)

(:cell:)

(:tableend:)

June 09, 2015, at 10:14 AM by 193.49.104.233 -
Changed line 8 from:
  • Dk the class of graphs with mximum degree at most k,
to:
  • Dk the class of graphs with maximum degree at most k,
June 09, 2015, at 10:14 AM by 193.49.104.233 -
Changed lines 5-9 from:
  • (:latex:) $\cal I$
      \begin{equation}
         \prod_{n=2}^N\frac{n}{n-1} = N
      \end{equation}
      (:latexend:)
to:
  • I the class of empty graphs,
  • F the class of forests,
  • Fk the class of forests with maximum degree at most k,
  • Dk the class of graphs with mximum degree at most k,
  • dk the class of k-degenerate graphs
June 09, 2015, at 10:10 AM by 193.49.104.233 -
Changed lines 5-9 from:
  • $\cal I$
to:
  • (:latex:) $\cal I$
      \begin{equation}
         \prod_{n=2}^N\frac{n}{n-1} = N
      \end{equation}
      (:latexend:)
June 09, 2015, at 10:06 AM by 193.49.104.233 -
Changed lines 2-5 from:

to:

Let us consider the following classes of graphs:

  • $\cal I$
June 09, 2015, at 10:06 AM by 193.49.104.233 -
June 09, 2015, at 09:54 AM by 193.49.104.233 -
Changed line 1 from:

Vertex-partitions of planar graphs

to:

Vertex-partitions of planar graphs

June 09, 2015, at 09:54 AM by 193.49.104.233 -
Added lines 1-2:

Vertex-partitions of planar graphs



LIRMM

HAL-LIRMM

Dept. Info UM2

GT Graphes

Vertex-partitions of planar graphs

The 3-Color Problem

Around the world