Improper coloring of graphs on surfaces

DOI10.1002/JGT.22418MaRDI QIDQ5379836zbMATH OpenOpenAlexWikidataFDO

Authors Ilkyoo Choi, L. Esperet

Publication date 14 June 2019

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

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

zbMATH Keywords

defective coloringgraphs on surfacesimproper coloring

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A graph $G$ is $(d_1,ldots,d_k)$-colorable if its vertex set can be partitioned into $k$ sets $V_1,ldots,V_k$, such that for each $iin1,ldots,k$, the subgraph of $G$ induced by $V_i$ has maximum degree at most $d_i$. The Four Color Theorem states that every planar graph is $(0,0,0,0)$-colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is $(2,2,2)$-colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus $g>0$ is $(0,0,0,9g-4)$-colorable and $(2,2,9g-4)$-colorable. Moreover, these graphs are also $(0,0,O(sqrtg),O(sqrtg))$-colorable and $(2,O(sqrtg),O(sqrtg))$-colorable. We also prove that every triangle-free graph that is embeddable on a surface of Euler genus $g$ is $(0,0,O(g))$-colorable. This is an extension of Gr"{o}tzsch's Theorem, which states that triangle-free planar graphs are $(0,0,0)$-colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus $g$ is $(0,O(sqrtg))$-colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on $g$ are tight up to a constant multiplicative factor.

Recommendations

• Improper choosability of graphs embedded on the surface of genus r
• Hyperbolic families and coloring graphs on surfaces
• A note on defective colorings of graphs in surfaces
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Edge colorings of graphs embeddable in a surface of low genus

Cited in

(22)

• Improper choosability of graphs embedded on the surface of genus r
• Colouring planar graphs with bounded monochromatic components
• Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
• Clustered variants of Hajós' conjecture
• The number of defective colorings of graphs on surfaces
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• A note on defective colorings of graphs in surfaces
• From the plane to higher surfaces
• Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
• Parameterized (approximate) defective coloring
• Defective and clustered choosability of sparse graphs
• Coloring parameters for graphs on surfaces
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Clustered 3-colouring graphs of bounded degree
• Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable
• Graph partitions under average degree constraint
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Colouring strong products
• Structural parameterizations for two bounded degree problems revisited
• Coloring face hypergraphs on surfaces
• Defective and clustered colouring of graphs with given girth
• Clustered coloring of graphs excluding a subgraph and a minor

This page was built for publication: Improper coloring of graphs on surfaces

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