An introduction to the discharging method via graph coloring
From MaRDI portal
Abstract: We provide a "how-to" guide to the use and application of the Discharging Method. Our aim is not to exhaustively survey results proved by this technique, but rather to demystify the technique and facilitate its wider use, using applications in graph coloring as examples. Along the way, we present some new proofs and new problems.
Recommendations
Cites work
- 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
- 2-distance coloring of sparse graphs
- 3-list-coloring planar graphs of girth 5
- 6-Star-Coloring of Subcubic Graphs
- 8-star-choosability of a graph with maximum average degree less than 3
- A bound on the chromatic number of the square of a planar graph
- A lower bound for the independence number of a planar graph
- A note on the three color problem
- A short list color proof of Grötzsch's theorem
- A sufficient condition for a planar graph to be class I
- A sufficient condition for a plane graph with maximum degree 6 to be class 1
- Acyclic 3-choosability of sparse graphs with girth at least 7
- Acyclic 4-choosability of planar graphs with girth at least 5
- Acyclic 4-choosability of planar graphs with no 4- and 5-cycles
- Acyclic 4-choosability of planar graphs withot cycles of specific lengths
- Acyclic 5-choosability of planar graphs without 4-cycles
- Acyclic 5-choosability of planar graphs without adjacent short cycles
- Acyclic colorings of planar graphs
- Acyclic list 7‐coloring of planar graphs
- Choosability and edge choosability of planar graphs without five cycles
- Choosability conjectures and multicircuits
- Choosability of the square of a planar graph with maximum degree four
- Circular \((5,2)\)-coloring of sparse graphs
- Circular chromatic number: A survey
- Coloring edges of graphs embedded in a surface of characteristic zero.
- Coloring Powers of Planar Graphs
- Coloring squares of planar graphs with girth six
- Coloring the square of a planar graph
- Coloring the square of a sparse graph G with almost (G) colors
- Coloring with no 2-colored \(P_4\)'s
- Colorings of plane graphs: a survey
- Counterexamples to the list square coloring conjecture
- Covering and packing in graphs IV: Linear arboricity
- Covering planar graphs with forests
- Decomposition of Finite Graphs Into Forests
- Describing 3-faces in normal plane maps with minimum degree 4
- Describing (d-2)-stars at d-vertices, d 5, in normal plane maps
- Edge choosability of planar graphs without small cycles
- Edge coloring of graphs with small average degrees
- Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles
- Every planar graph is 5-choosable
- Every planar graph with maximum degree 7 is of class 1
- Every Planar Map is Four Colorable
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Fire Containment in Planar Graphs
- Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs
- Graphs of degree 4 are 5-edge-choosable
- Graphs with maximum degree 17 and maximum average degree less than 3 are list 2-distance ( +2)-colorable
- Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Homomorphisms from sparse graphs with large girth.
- scientific article; zbMATH DE number 434910 (Why is no real title available?)
- scientific article; zbMATH DE number 4135967 (Why is no real title available?)
- scientific article; zbMATH DE number 3989394 (Why is no real title available?)
- scientific article; zbMATH DE number 4075098 (Why is no real title available?)
- scientific article; zbMATH DE number 3717365 (Why is no real title available?)
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 1299961 (Why is no real title available?)
- scientific article; zbMATH DE number 1342018 (Why is no real title available?)
- scientific article; zbMATH DE number 1523257 (Why is no real title available?)
- scientific article; zbMATH DE number 1534644 (Why is no real title available?)
- scientific article; zbMATH DE number 1882350 (Why is no real title available?)
- scientific article; zbMATH DE number 5875579 (Why is no real title available?)
- scientific article; zbMATH DE number 3273761 (Why is no real title available?)
- scientific article; zbMATH DE number 3284071 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- I,F-partitions of sparse graphs
- Improper choosability of graphs and maximum average degree
- Injective colorings of graphs with low average degree
- Injective colorings of sparse graphs
- Largest planar graphs of diameter two and fixed maximum degree
- Light subgraphs of graphs embedded in the plane. A survey
- Linear choosability of sparse graphs
- List 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six
- List coloring the square of sparse graphs with large degree
- List Colouring Squares of Planar Graphs
- List colourings of planar graphs
- List Dynamic Coloring of Sparse Graphs
- List edge and list total colourings of multigraphs
- List-coloring the square of a subcubic graph
- List-colourings of graphs
- Near-proper vertex 2-colorings of sparse graphs
- Note to the paper of Grünbaum on acyclic colorings
- Nowhere-zero 3-flows and modulo \(k\)-orientations
- On a 1,2 conjecture
- On acyclic colorings of planar graphs
- On Light Edges and Triangles in Planar Graphs of Minimum Degree Five
- On the size of critical graphs with maximum degree 8
- On the size of edge chromatic critical graphs
- On the total coloring of planar graphs.
- Ore's conjecture for k=4 and Grötzsch's theorem
- Planar graphs of maximum degree seven are Class I
- Planar graphs with 8 are (+1)-edge-choosable
- Planar graphs with maximum degree \(\Delta \geq 9\) are \((\Delta +1)\)-edge-choosable--a short proof
- Planar graphs without 4- and 5-cycles are acyclically 4-choosable
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- Recent developments in circular colouring of graphs
- Some remarks on a paper by Vizing on critical graphs
- Some sufficient conditions for a planar graph of maximum degree six to be Class 1
- Star coloring high girth planar graphs
- Star coloring of graphs
- Star coloring of sparse graphs
- Steinberg's conjecture is false
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
- Structural theorem on plane graphs with application to the entire coloring number
- Sufficient conditions for planar graphs to be 2-distance (\(\Delta+1\))-colourable
- Sufficient conditions for the minimum 2-distance colorability of plane graphs of girth 6
- Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\)
- The 1,2,3-conjecture and 1,2-conjecture for sparse graphs
- The average degree of a multigraph critical with respect to edge or total choosability
- The average degree of an edge‐chromatic critical graph II
- The four-colour theorem
- The linear arboricity of graphs
- The linear arboricity of planar graphs of maximum degree seven is four
- The linear arboricity of some regular graphs
- The list chromatic index of a bipartite multigraph
- The NP-Completeness of Edge-Coloring
- Three-coloring triangle-free planar graphs in linear time
Cited in
(57)- On the strong chromatic index of sparse graphs
- Light paths and edges in families of outer-1-planar graphs
- Injective choosability of subcubic planar graphs with girth 6
- On acyclic 4-choosability of planar graphs without cycles of length 4, 7 and 9
- On weak flexibility in planar graphs
- Remarks on proper conflict-free colorings of graphs
- On the largest planar graphs with everywhere positive combinatorial curvature
- 3-vertices with fewest 2-neighbors in plane graphs with no long paths of 2-vertices
- The chromatic number of signed graphs with bounded maximum average degree
- On the structure of essentially-highly-connected polyhedral graphs
- Additive list coloring of planar graphs with given girth
- All tight descriptions of 3-paths in plane graphs with girth 8
- Flexibility of planar graphs -- sharpening the tools to get lists of size four
- Odd graph and its applications to the strong edge coloring
- Planar graphs with girth 20 are additively 3-choosable
- All tight descriptions of 3-paths centered at 2-vertices in plane graphs with girth at least 6
- \((4,2)\)-choosability of planar graphs with forbidden structures
- On star 5-colorings of sparse graphs
- Degeneracy and colorings of squares of planar graphs without 4-cycles
- All tight descriptions of 3-paths in plane graphs with girth at least 7
- Cyclic coloring of plane graphs with maximum face size 16 and 17
- Independent bondage number of planar graphs with minimum degree at least 3
- The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
- Application of discharging method in graph colorings theory
- Light structures in infinite planar graphs without the strong isoperimetric property
- Decomposing the edges of a graph into simpler structures
- The number of small-degree vertices in matchstick graphs
- Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable
- Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable
- Saturation for the 3-uniform loose 3-cycle
- Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width
- A tight bound for independent domination of cubic graphs without 4‐cycles
- Tight description of faces of triangulations on the torus
- Square Coloring Planar Graphs with Automatic Discharging
- Total colorings-a survey
- A strengthening and an efficient implementation of Alon-Tarsi list coloring method
- Light 3-paths in 3-polytopes without adjacent triangles
- Density of identifying codes of hexagonal grids with finite number of rows
- Bounding clique size in squares of planar graphs
- Relaxation of Wegner's planar graph conjecture for maximum degree 4
- Planar graph with twin-width seven
- Optimal local identifying and local locating-dominating codes
- Light 3-faces in 3-polytopes without adjacent triangles
- On injective edge-coloring of graphs with maximum degree 4
- Proper additive choice number of planar graphs
- Description of edges incident to 3-faces in 3-polytopes without adjacent 3-faces
- Beyond the pseudoforest strong nine dragon tree theorem
- List packing and correspondence packing of planar graphs
- Tight description of faces in toroidal graphs with minimum degree at least 4
- On double Roman domination problem for several graph classes
- Injective edge chromatic index of sparse graphs
- Describing 3-faces in 3-polytopes without adjacent triangles
- Planar graphs with no incident triangles and no 4- or 5-cycles are (7:2)-colorable
- Edge-coloring sparse graphs with Colors in quasilinear time
- On the density of (1, )-locating-dominating codes in the infinite square grid
- On (1, l)-locating-dominating codes in infinite triangular grid
- Homomorphisms of sparse signed graphs
This page was built for publication: An introduction to the discharging method via graph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507506)
