Square Coloring Planar Graphs with Automatic Discharging

DOI10.1137/22M1492623MaRDI QIDQ6141869zbMATH OpenWikidataFDO

Authors Nicolas Bousquet, Quentin Deschamps, Lucas de Meyer, Théo Pierron

Publication date 23 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

automatic proofdischargingplanar graphssquare coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Linear programming (90C05)

Abstract: The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometimes given to a computer for verification. However, it is much less common to use a computer to actively look for a discharging proof. In this paper, we use a Linear Programming approach to automatically look for a discharging proof. While our system is not entirely autonomous, we manage to make some progress towards Wegner's conjecture for distance-$2$ coloring of planar graphs, by showing that $12$ colors are sufficient to color at distance $2$ every planar graph with maximum degree $4$.

Recommendations

• An introduction to the discharging method via graph coloring
• Improved square coloring of planar graphs
• An optimal square coloring of planar graphs
• Coloring the square of a planar graph

Cites work

• A computer-assisted proof of the Feigenbaum conjectures
• A unified approach to distance-two colouring of graphs on surfaces
• An introduction to the discharging method via graph coloring
• Choosability of the square of a planar graph with maximum degree four
• Computer solution to the 17-point Erdős-Szekeres problem
• Cyclic coloring of plane graphs with maximum face size 16 and 17
• Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable
• Every planar map is four colorable
• Flag Algebras: A First Glance
• Generation and properties of snarks
• Generation of cubic graphs
• Improved square coloring of planar graphs
• List Colouring Squares of Planar Graphs
• Minimum-weight triangulation is NP-hard
• Painting squares in \(\Delta^2-1\) shades
• Robbins algebras are Boolean: A revision of McCune's computer-generated solution of Robbins problem
• Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer
• Steinberg's conjecture is false
• The Non-Existence of Finite Projective Planes of Order 10
• The resolution of Keller's conjecture
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
• Third case of the cyclic coloring conjecture
• Wegner's conjecture on 2-distance coloring

Cited in

(4)

• Relaxation of Wegner's planar graph conjecture for maximum degree 4
• Improved 2-distance coloring of planar graphs with maximum degree 5
• On 2-distance ( 2 + 6)-coloring of planar graphs
• Coloring squares of planar graphs with small maximum degree

This page was built for publication: Square Coloring Planar Graphs with Automatic Discharging

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6141869)