On 1-improper 2-coloring of sparse graphs
From MaRDI portal
Publication:393935
DOI10.1016/j.disc.2013.07.014zbMath1281.05060OpenAlexW2198303752MaRDI QIDQ393935
Matthew P. Yancey, Oleg V. Borodin, Alexandr V. Kostochka
Publication date: 24 January 2014
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2013.07.014
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)
Related Items (32)
A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable ⋮ Path partitioning planar graphs of girth 4 without adjacent short cycles ⋮ I,F-partitions of sparse graphs ⋮ Unnamed Item ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ Colorings of plane graphs without long monochromatic facial paths ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Partitioning sparse graphs into an independent set and a graph with bounded size components ⋮ On the computational complexity of the bipartizing matching problem ⋮ Path partition of planar graphs with girth at least six ⋮ Parameterized (Approximate) Defective Coloring ⋮ Graph partitions under average degree constraint ⋮ Sparse critical graphs for defective DP-colorings ⋮ (1,k)-Coloring of Graphs with Girth at Least Five on a Surface ⋮ On 2-defective DP-colorings of sparse graphs ⋮ Defective DP-colorings of sparse multigraphs ⋮ Planar graphs with girth at least 5 are \((3, 5)\)-colorable ⋮ Path partitioning planar graphs with restrictions on short cycles ⋮ Defective DP-colorings of sparse simple graphs ⋮ Splitting a planar graph of girth 5 into two forests with trees of small diameter ⋮ WORM colorings of planar graphs ⋮ Near-colorings: non-colorable graphs and NP-completeness ⋮ Islands in Graphs on Surfaces ⋮ Maximum average degree and relaxed coloring ⋮ A Brooks-type result for sparse critical graphs ⋮ Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions ⋮ Note on improper coloring of $1$-planar graphs ⋮ Defective and clustered choosability of sparse graphs ⋮ Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths ⋮ Planar graphs with girth at least 5 are \((3, 4)\)-colorable ⋮ Vertex Partitions into an Independent Set and a Forest with Each Component Small ⋮ Defective Coloring on Classes of Perfect Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \((k,1)\)-coloring of sparse graphs
- \((k,j)\)-coloring of sparse graphs
- Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Defective 2-colorings of sparse graphs
- Path partitions of planar graphs
- List strong linear 2-arboricity of sparse graphs
- Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- Globally sparse vertex‐ramsey graphs
- Improper choosability of graphs and maximum average degree
This page was built for publication: On 1-improper 2-coloring of sparse graphs
