Weak degeneracy of graphs

DOI10.1002/JGT.22938MaRDI QIDQ6047953zbMATH OpenOpenAlexFDO

Authors Anton Bernshteyn, Eugene Lee

Publication date 10 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

DP-coloringgraph coloringgraph degeneracygreedy algorithmsmaximum degreeweak degeneracy

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Motivated by the study of greedy algorithms for graph coloring, we introduce a new graph parameter, which we call weak degeneracy. By definition, every $d$-degenerate graph is also weakly $d$-degenerate. On the other hand, if $G$ is weakly $d$-degenerate, then $chi(G)leqd+1$ (and, moreover, the same bound holds for the list-chromatic and even the DP-chromatic number of $G$). It turns out that several upper bounds in graph coloring theory can be phrased in terms of weak degeneracy. For example, we show that planar graphs are weakly $4$-degenerate, which implies Thomassen's famous theorem that planar graphs are $5$-list-colorable. We also prove a version of Brooks's theorem for weak degeneracy: a connected graph $G$ of maximum degree $dgeq3$ is weakly $(d-1)$-degenerate unless $Gcong{K}_{d+1}$. (By contrast, all $d$-regular graphs have degeneracy $d$.) We actually prove an even stronger result, namely that for every $dgeq3$, there is $epsilon>0$ such that if $G$ is a graph of weak degeneracy at least $d$, then either $G$ contains a $(d+1)$-clique or the maximum average degree of $G$ is at least $d+epsilon$. Finally, we show that graphs of maximum degree $d$ and either of girth at least $5$ or of bounded chromatic number are weakly $(d-Omega(sqrtd))$-degenerate, which is best possible up to the value of the implied constant.

Recommendations

• Weak-rupture degree of graphs
• The weak rupture degree of graphs
• A theory of degeneracy graphs
• scientific article; zbMATH DE number 89070
• On the weak-integrity of graphs
• Weak saturation numbers for graphs
• scientific article; zbMATH DE number 5626049
• Weakly triangulated graphs
• On weak domination in graphs
• On weak domination in graphs

Cites work

• Colouring graphs with forbidden bipartite subgraphs
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Every planar graph is 5-choosable
• Explicit construction of regular graphs without small cycles
• Explicit constructions of graphs without short cycles and low density codes
• Graph colouring and the probabilistic method
• Graph theory
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• List colourings of planar graphs
• On chromatic number of graphs and set-systems
• On DP-coloring of graphs and multigraphs
• On regular bipartite-preserving supergraphs
• On-line DP-coloring of graphs
• The asymptotic behavior of the correspondence chromatic number
• The probabilistic method

Cited in

(18)

• Weakly cospectral graphs
• Improved bounds for weak coloring numbers
• scientific article; zbMATH DE number 5626049 (Why is no real title available?)
• scientific article; zbMATH DE number 89070 (Why is no real title available?)
• Weak degeneracy of planar graphs and locally planar graphs
• The relation between the harmonic index and some coloring parameters
• Weak degeneracy of planar graphs without 4- and 6-cycles
• Weak degeneracy of regular graphs
• Toroidal graphs without K₅^- and 6-cycles
• Planar graphs without 4-, 7-, 9-cycles and 5-cycles normally adjacent to 3-cycles
• Weak degeneracy of line graphs of planar graphs
• Weak degeneracy of the square of K₄-minor free graphs
• Paintability of r-chromatic graphs
• Planar graphs with distance of 3-cycles at least 2 and no cycles of lengths 5, 6, 7
• Weak degeneracy of the square of planar graphs with given girth
• Weak-strict degeneracy on line graphs of planar graphs
• Weak degeneracy of planar graphs
• Arc-weighted acyclic orientation of graphs

This page was built for publication: Weak degeneracy of graphs

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