, Now by Lemma 8, there is at least one big vertex outside of S that has a neighbour in S. Note that if there are at least two of these vertices, or if one of them has at least two neighbours in S
, Therefore S is a bud. In this case, S ends up with a charge of at least ?. We will
, For every big vertex v, v gives 1 ? 2 to each of its sons, does not give anything to its father (if it has one), and gives 1? 2 to its other 2-neighbours
, The common pot gives to every internal 2-vertex
, Every vertex has non-negative charge at the end of the procedure, Lemma, vol.17
Note that by what precedes every small 3 +-vertex v has non-negative charge. Every 2-vertex that is not in L receives 1? 2 from each of its neighbours. Every light 2-vertex that is not adjacent to a 2-vertex (i.e. every 2-vertex of L that is not an internal 2-vertex) receives 1 ? 2 from its father and from its other neighbour ,
Every internal 2-vertex receives 1 ? 2 from its father and from the common pot ,
, Let c(v) be the initial charge of v, and c (v) be the final charge of v. Suppose by contradiction that c (v) < 0. By Lemma 9, vertex v has at most k ? 1 sons. Moreover, if v has k ? 1 sons, then its last neighbour is either the father of v
, ? 1 sons, then v gives 1 ? 2 to each of its k ? 1 sons, and 2(k ? d ? 1) to the common pot, therefore c (v) = c(v) ? (1 ? 2)(k ? 1) + 2(k ? d ? 1), and thus as c (v) < 0
By Lemma 16, this charge is at least times the number of internal 2-vertices. The common pot gives to each internal 2-vertex, therefore it has non-negative charge at the end of the procedure, the electronic journal of combinatorics, vol.25, issue.1, 2018. ,
Every planar map is four colorable. Part 1: Discharging, Illinois Journal of Mathematics, vol.21, pp.429-490, 1977. ,
Every planar map is four colorable. Part 2: Reducibility, Illinois Journal of Mathematics, vol.21, pp.491-567, 1977. ,
A proof of Grünbaum's conjecture on the acyclic 5-colorability of planar graphs (Russian), Dokl. Akad. Nauk SSSR, vol.231, issue.1, pp.18-20, 1976. ,
On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph (Russian), Diskretnyi Analiz i Issledovanie Operatsii, vol.8, issue.4, pp.34-53, 2001. ,
Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k, Journal of Graph Theory, vol.65, issue.2, pp.83-93, 2010. ,
URL : https://hal.archives-ouvertes.fr/hal-00377372
Vertex partitions of sparse graphs into an independent vertex set and subgraph of maximum degree at most one (Russian), Siberian Mathematical Journal, vol.52, pp.796-801, 2011. ,
Defective 2-colorings of sparse graphs, Journal of Combinatorial Theory, Series B, vol.104, pp.72-80, 2014. ,
A complexity dichotomy for the coloring of sparse graphs, Journal of Graph Theory, vol.73, issue.1, pp.85-102, 2013. ,
URL : https://hal.archives-ouvertes.fr/lirmm-00736468
How to orient the edges of a graph, In Combinatorics, I, Colloq. Math. Soc. János Bolyai, vol.18, pp.353-364, 1978. ,
Improper coloring of sparse graphs with a given girth, I:(0, 1)-colorings of triangle-free graphs, European Journal of Combinatorics, vol.42, pp.26-48, 2014. ,
Near-colorings: Non-colorable graphs and npcompleteness, The Electronic Journal of Combinatorics, vol.22, issue.1, 2015. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01263770
On the linear vertex-arboricity of a plane graph, the electronic journal of combinatorics, vol.14, issue.1, pp.73-75, 1990. ,