An introduction to the discharging method via graph coloring

DOI10.1016/j.disc.2016.11.022zbMath1355.05104arXiv1306.4434OpenAlexW2559217904MaRDI QIDQ507506

Daniel W. Cranston, Douglas B. West

Publication date: 6 February 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.4434

zbMATH Keywords

graph coloringedge-coloringlight subgraphplanar graphdischarging methodmaximum average degree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (35)

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 strong chromatic index of sparse graphs ⋮ 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 ⋮ On the structure of essentially-highly-connected polyhedral graphs ⋮ Cyclic coloring of plane graphs with maximum face size 16 and 17 ⋮ Additive list coloring of planar graphs with given girth ⋮ \((4,2)\)-choosability of planar graphs with forbidden structures ⋮ All tight descriptions of 3-paths in plane graphs with girth 8 ⋮ Independent bondage number of planar graphs with minimum degree at least 3 ⋮ Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable ⋮ Plane Graphs without 4- and 5-Cycles and without Ext-Triangular 7-Cycles are 3-Colorable ⋮ 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 ⋮ The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles ⋮ 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 ⋮ The number of small-degree vertices in matchstick graphs ⋮ Flexibility of planar graphs -- sharpening the tools to get lists of size four ⋮ Light paths and edges in families of outer-1-planar graphs ⋮ Injective choosability of subcubic planar graphs with girth 6 ⋮ Odd graph and its applications to the strong edge coloring ⋮ On acyclic 4-choosability of planar graphs without cycles of length 4, 7 and 9 ⋮ Planar graphs with girth 20 are additively 3-choosable ⋮ Homomorphisms of sparse signed graphs ⋮ All tight descriptions of 3-paths centered at 2-vertices in plane graphs with girth at least 6 ⋮ On weak flexibility in planar graphs ⋮ Remarks on proper conflict-free colorings of graphs ⋮ On the largest planar graphs with everywhere positive combinatorial curvature

Cites Work

• I,F-partitions of sparse graphs
• Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors
• Steinberg's conjecture is false
• Describing \((d-2)\)-stars at \(d\)-vertices, \(d\leq 5\), in normal plane maps
• Graphs with maximum degree \(\varDelta\geq 17\) and maximum average degree less than 3 are list 2-distance \((\varDelta +2)\)-colorable
• Describing 3-faces in normal plane maps with minimum degree 4
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• The \(1,2,3\)-conjecture and \(1,2\)-conjecture for sparse graphs
• Injective colorings of graphs with low average degree
• Largest planar graphs of diameter two and fixed maximum degree
• List colourings of planar graphs
• Acyclic 3-choosability of sparse graphs with girth at least 7
• Injective colorings of sparse graphs
• Planar graphs with maximum degree \(\Delta \geq 9\) are \((\Delta +1)\)-edge-choosable--a short proof
• List coloring the square of sparse graphs with large degree
• Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\)
• The average degree of a multigraph critical with respect to edge or total choosability
• On the size of critical graphs with maximum degree 8
• Star coloring high girth planar graphs
• List 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six
• 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
• List-colourings of graphs
• The linear arboricity of graphs
• Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs
• Note to the paper of Grünbaum on acyclic colorings
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• On acyclic colorings of planar graphs
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Every planar graph is 5-choosable
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• List edge and list total colourings of multigraphs
• The four-colour theorem
• On the size of edge chromatic critical graphs
• A short list color proof of Grötzsch's theorem
• Coloring edges of graphs embedded in a surface of characteristic zero.
• Edge coloring of graphs with small average degrees
• Homomorphisms from sparse graphs with large girth.
• Choosability and edge choosability of planar graphs without five cycles
• A sufficient condition for a plane graph with maximum degree 6 to be class 1
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Covering planar graphs with forests
• A note on the three color problem
• Edge choosability of planar graphs without small cycles
• A lower bound for the independence number of a planar graph
• Planar graphs of maximum degree seven are Class I
• Coloring with no 2-colored \(P_4\)'s
• The list chromatic index of a bipartite multigraph
• 3-list-coloring planar graphs of girth 5
• Light subgraphs of graphs embedded in the plane. A survey
• Colorings of plane graphs: a survey
• Planar graphs without 4- and 5-cycles are acyclically 4-choosable
• Linear choosability of sparse graphs
• Sufficient conditions for the minimum 2-distance colorability of plane graphs of girth 6
• Coloring squares of planar graphs with girth six
• Circular \((5,2)\)-coloring of sparse graphs
• A sufficient condition for a planar graph to be class I
• A bound on the chromatic number of the square of a planar graph
• Some sufficient conditions for a planar graph of maximum degree six to be Class 1
• Sufficient conditions for planar graphs to be 2-distance (\(\Delta+1\))-colourable
• Choosability of the square of a planar graph with maximum degree four
• A Planar linear arboricity conjecture
• Planar graphs with $\Delta\geq 8$ are ($\Delta+1$)-edge-choosable
• Star coloring of graphs
• Acyclic 5-choosability of planar graphs without adjacent short cycles
• List Colouring Squares of Planar Graphs
• The linear arboricity of planar graphs of maximum degree seven is four
• List-coloring the square of a subcubic graph
• Star coloring of sparse graphs
• The linear arboricity of some regular graphs
• On the total coloring of planar graphs.
• The NP-Completeness of Edge-Coloring
• Covering and packing in graphs IV: Linear arboricity
• Every Planar Map is Four Colorable
• Some remarks on a paper by Vizing on critical graphs
• On Light Edges and Triangles in Planar Graphs of Minimum Degree Five
• Coloring Powers of Planar Graphs
• Acyclic list 7‐coloring of planar graphs
• Structural theorem on plane graphs with application to the entire coloring number
• Graphs of degree 4 are 5-edge-choosable
• Coloring the square of a planar graph
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• 6-Star-Coloring of Subcubic Graphs
• Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles
• Counterexamples to the List Square Coloring Conjecture
• List Dynamic Coloring of Sparse Graphs
• Edge-choosability and total-choosability of planar graphs with no adjacent 3-cycles
• Fire Containment in Planar Graphs
• The average degree of an edge‐chromatic critical graph II
• Improper choosability of graphs and maximum average degree
• Decomposition of Finite Graphs Into Forests
• Acyclic 5-choosability of planar graphs without 4-cycles
• Acyclic colorings of planar graphs
• Circular chromatic number: A survey
• Every planar graph with maximum degree 7 is of class 1
• Choosability conjectures and multicircuits
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An introduction to the discharging method via graph coloring