## Site.VertexPartition History

Hide minor edits - Show changes to markup

(I,F5) | F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. |

(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 |

(I,F3) | F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. |

(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 |

(I,F2) | F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. |

(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 |

(I,F5) |

(I,F5) |

(I,F3) |

(I,F3) |

(I,F2) |

(I,F2) |

(I,F5) |

(I,F3) |

(I,F2) |

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

(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 |

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

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

(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 |

(O12,O12) | L. Esperet and P. Ochem.Islands in graphs on surfaces. http://arxiv.org/pdf/1402.2475v3.pdf |

(O12,O12) | L. Esperet and P. Ochem. Islands in graphs on surfaces. http://arxiv.org/pdf/1402.2475v3.pdf |

- dk the class of k-degenerate graphs

- dk the class of k-degenerate graphs,
- Ok the class of graphs of order k.

(O12,O12) | L. Esperet and P. Ochem.Islands in graphs on surfaces. http://arxiv.org/pdf/1402.2475v3.pdf |

Thanks to Ilkyoo Choi, Pascal Ochem.

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

(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 |

(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 |

Thanks to Pascal Ochem.

Thanks to Ilkyoo Choi, Pascal Ochem.

(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

(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 |

- P the class of paths,
- Pk the class of paths ol length at most k,

(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

Thank you to Pascal Ochem.

Thanks to Pascal Ochem.

Thank you to Pascal Ochem

Thank you to Pascal Ochem.

.

### Acknowledgement

### Acknowledgements

### Acknowledgment

### Acknowledgement

### Acknowledgment

Thank you to Pascal Ochem

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

M. Montassier and P. Ochem. Near-colorings: non-colorable graphs and NP-completness. http://arxiv.org/abs/1306.0752 |

M. Montassier and P. Ochem. Near-colorings: non-colorable graphs and NP-completness. Electronic Journal of Combinatorics,Volume 22, Issue 1, 2015. |

10 | (I,D1) ? | Open question. |

10 | (I,D1) ? | Open question. |

10 | (I,D1) ? | Open question. |

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

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

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

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

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

M. Montassier and P. Ochem. Near-colorings: non-colorable graphs and NP-completness. http://arxiv.org/abs/1306.0752 |

no | O.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. |

O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

no (I,Fd) for any d | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

no | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

no (I,Fd) for any d | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

no (I,Fd) for any d | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

no (I,Fd) for any d | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

no (I,Fd) for any d | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

(I,Fd) for any d | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

no (I,Fd) for any d | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

(I,Fd) for any d | O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. |

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.

### Results

.

comment .

.

comment .

## .

.

## .

## coucou

## coucou

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

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

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

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

(D1,D1) | O.V. Borodin, A. Kostochka, M. Yancey. On 11-improper 22-coloring of sparse graphs. Discrete Mathematics, 313(22):2638-2649, 2013. |

(D1,D1) | O.V. Borodin, A. Kostochka, M. Yancey. On 1-improper 2-coloring of sparse graphs. Discrete Mathematics, 313(22):2638-2649, 2013. |

(D1,D1) | O.V. Borodin, A. Kostochka, M. Yancey. On 11-improper 22-coloring of sparse graphs. Discrete Mathematics, 313(22):2638-2649, 2013. |

(D1,D1) | F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006. |

9 | |

10 |

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

- S the class of star forests,
- Sk the class of star forests with maximum degree at most k,

7 | |

8 |

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

(D2,D2) | F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006. |

(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 |

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

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

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

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

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

(D1,D10) | .'''(1,k)-coloring of graphs with girth at least 5 on a surface |

(D1,D10) | H. Choi, I. Choi, J. Jeong, G. Suh.'''(1,k)-coloring of graphs with girth at least 5 on a surface |

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

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

(D1,D10) |

(D1,D10) | .'''(1,k)-coloring of graphs with girth at least 5 on a surface |

'''. arXiv:1412.0344, 2014.

(D3,D5) |

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

(D4,D4) | F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree, Journal of Graph Theory 52(3):181-199, 2006. |

(D4,D4) | F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006. |

(D4,D4) |

(D4,D4) | F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree, Journal of Graph Theory 52(3):181-199, 2006. |

(D2,D6) | O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory Series B, 104:72-80, 2014. |

(D2,D6) | O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014. |

(I,d2) | Folklore |

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

(F,F) | Folklore | |

(I,d2) | Folklore |

(F,F) | Folklore | |

(I,d2) | Folklore |

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

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 |

4 |

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

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

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

(F2,F2,F,2) |

(F2,F2,F2) |

(I,d3) |

(I,d3) | |

4 |

Appel K., Haken W., Koch J. Every Planar Map is Four Colorable Part II. Reducibility, Illinois Journal of Mathematics 21: 491–567, 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,F,2) | ||

(F,d2) | ||

(I,d3) |

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

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

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

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

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

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

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

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

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

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

3 | (I,I,I,I) | Appel |

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

Girth | Vertex-partitions | References |

Girth | Vertex-partitions | References |

Girth | Vertex-partitions | References |

Girth | Vertex-partitions | References |

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

Girth

(:cell:)

Vertex-partitions

(:cell:)

References

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

Girth | Vertex-partitions | References |

3 | (I,I,I,I) | Appel |

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

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

3

(I,I,I,I)

Appel,

Girth

Girth

Vertex-partition

Vertex-partitions

Reference

References

Girth

Vertex-partition

Reference

- dk the class of k-degenerate graphs

- dk the class of k-degenerate graphs

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

(:cell:)

(:cell:)

(:cellnr:)

(:cell:)

(:cell:)

(:tableend:)

- Dk the class of graphs with mximum degree at most k,

- Dk the class of graphs with maximum degree at most k,

- (:latex:) $\cal I$

\begin{equation} \prod_{n=2}^N\frac{n}{n-1} = N \end{equation} (:latexend:)

- 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

- $\cal I$

- (:latex:) $\cal I$

\begin{equation} \prod_{n=2}^N\frac{n}{n-1} = N \end{equation} (:latexend:)

Let us consider the following classes of graphs:

- $\cal I$