Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
From MaRDI portal
Publication:404440
DOI10.1016/j.ejc.2014.05.003zbMath1297.05083OpenAlexW1979457746MaRDI QIDQ404440
Xuding Zhu, Jae-Hoon Kim, Alexandr V. Kostochka
Publication date: 4 September 2014
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2014.05.003
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 (22)
Path partitioning planar graphs of girth 4 without adjacent short cycles ⋮ Unnamed Item ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ Colouring planar graphs with bounded monochromatic components ⋮ An (F1,F4)‐partition of graphs with low genus and girth at least 6 ⋮ Parameterized (Approximate) Defective Coloring ⋮ On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree ⋮ Graph partitions under average degree constraint ⋮ Sparse critical graphs for defective DP-colorings ⋮ On 2-defective DP-colorings of sparse graphs ⋮ Defective DP-colorings of sparse multigraphs ⋮ Path partitioning planar graphs with restrictions on short cycles ⋮ Defective DP-colorings of sparse simple graphs ⋮ Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable ⋮ Splitting a planar graph of girth 5 into two forests with trees of small diameter ⋮ Near-colorings: non-colorable graphs and NP-completeness ⋮ Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions ⋮ Relaxed equitable colorings of planar graphs with girth at least 8 ⋮ Defective and clustered choosability of sparse graphs ⋮ Vertex partitions of \((C_3, C_4, C_6)\)-free planar graphs ⋮ An \((F_3,F_5)\)-partition of planar graphs with girth at least 5 ⋮ Defective Coloring on Classes of Perfect Graphs
Cites Work
- Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
- Path partitions of planar graphs
- Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions
- Limits of Near-Coloring of Sparse Graphs
- Globally sparse vertex‐ramsey graphs
- A Complexity Dichotomy for the Coloring of Sparse Graphs
This page was built for publication: Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
