Improper coloring of sparse graphs with a given girth. I: (0,1)-colorings of triangle-free graphs
DOI10.1016/J.EJC.2014.05.003zbMATH Open1297.05083OpenAlexW1979457746MaRDI QIDQ404440FDOQ404440
Jaehoon Kim, Alexandr Kostochka, Xuding Zhu
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
Recommendations
- Improper coloring of sparse graphs with a given girth. II: Constructions
- Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
- \((k,1)\)-coloring of sparse graphs
- On 1-improper 2-coloring of sparse graphs
- Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\)
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)
Cites Work
- Path partitions of planar graphs
- Improper coloring of sparse graphs with a given girth. II: Constructions
- Globally sparse vertex‐ramsey graphs
- A Complexity Dichotomy for the Coloring of Sparse Graphs
- Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
- Limits of near-coloring of sparse graphs
Cited In (24)
- Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable
- An \((F_3,F_5)\)-partition of planar graphs with girth at least 5
- Parameterized (Approximate) Defective Coloring
- Near-colorings: non-colorable graphs and NP-completeness
- Vertex partitions of \((C_3, C_4, C_6)\)-free planar graphs
- Title not available (Why is that?)
- On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree
- Path partitioning planar graphs of girth 4 without adjacent short cycles
- Splitting a planar graph of girth 5 into two forests with trees of small diameter
- Partitioning planar graph of girth 5 into two forests with maximum degree 4.
- Path partitioning planar graphs with restrictions on short cycles
- Defective Coloring on Classes of Perfect Graphs
- On 1-improper 2-coloring of sparse graphs
- An (F1,F4)‐partition of graphs with low genus and girth at least 6
- On 2-defective DP-colorings of sparse graphs
- Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
- Graph partitions under average degree constraint
- Improper coloring of sparse graphs with a given girth. II: Constructions
- Sparse critical graphs for defective DP-colorings
- Defective and clustered choosability of sparse graphs
- Colouring planar graphs with bounded monochromatic components
- Relaxed equitable colorings of planar graphs with girth at least 8
- Defective DP-colorings of sparse multigraphs
- Defective DP-colorings of sparse simple graphs
This page was built for publication: Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404440)
