Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
From MaRDI portal
Publication:3728016
DOI10.1002/jgt.3190100207zbMath0596.05024OpenAlexW2009827511MaRDI QIDQ3728016
No author found.
Publication date: 1986
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.3190100207
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Related Items (only showing first 100 items - show all)
Defective colorings on k-uniform hypergraphs ⋮ Globally sparse vertex‐ramsey graphs ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ Improper Choosability and Property B ⋮ Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable ⋮ A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles ⋮ Parameterized (Approximate) Defective Coloring ⋮ 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into two forests with a specific condition ⋮ A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles ⋮ Decomposition of toroidal graphs without some subgraphs ⋮ Extended MSO model checking via small vertex integrity ⋮ Graph partitions under average degree constraint ⋮ Weak (2, 3)-decomposition of planar graphs ⋮ Sparse critical graphs for defective DP-colorings ⋮ Not all planar graphs are in PURE-4-DIR ⋮ On t-relaxed chromatic number of r-power paths ⋮ Deciding Relaxed Two-Colourability: A Hardness Jump ⋮ The t-Improper Chromatic Number of Random Graphs ⋮ Acyclic colorings of planar graphs ⋮ Unnamed Item ⋮ Locally planar graphs are 2-defective 4-paintable ⋮ Defective and clustered choosability of sparse graphs ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ On (s,t)-relaxed L(1,1)-labelling of trees ⋮ Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths ⋮ Unnamed Item ⋮ Some of My Favorite Coloring Problems for Graphs and Digraphs ⋮ Defective Coloring on Classes of Perfect Graphs ⋮ An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem ⋮ A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable ⋮ Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable ⋮ Every planar graph with girth at least 5 is \((1,9)\)-colorable ⋮ \((3, 1)^*\)-choosability of graphs of nonnegative characteristic without intersecting short cycles ⋮ A simple competitive graph coloring algorithm. III ⋮ Path choosability of planar graphs ⋮ A QUESTION ON RELAXED EQUITABLE COLORING ⋮ The number of defective colorings of graphs on surfaces ⋮ Fashion game on planar graphs ⋮ Dynamic \(F\)-free coloring of graphs ⋮ Defective 2-colorings of planar graphs without 4-cycles and 5-cycles ⋮ Unnamed Item ⋮ A \((3,1)^\ast\)-choosable theorem on planar graphs ⋮ Fractional, Circular, and Defective Coloring of Series-Parallel Graphs ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ Every planar graph is 1-defective \((9,2)\)-paintable ⋮ On the minimal reducible bound for outerplanar and planar graphs ⋮ Parameterized complexity of fair deletion problems ⋮ Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable ⋮ The relaxed game chromatic index of \(k\)-degenerate graphs ⋮ Partitions of graphs into cographs ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable ⋮ On 1-improper 2-coloring of sparse graphs ⋮ (\(1,1,0\))-coloring of planar graphs without cycles of length 4 and 6 ⋮ New restrictions on defective coloring with applications to Steinberg-type graphs ⋮ The relaxed edge-coloring game and \(k\)-degenerate graphs ⋮ Weighted improper colouring ⋮ On the computational complexity of the bipartizing matching problem ⋮ The t-improper chromatic number of random graphs ⋮ Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable ⋮ \((k,1)\)-coloring of sparse graphs ⋮ \((k,j)\)-coloring of sparse graphs ⋮ Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable ⋮ Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable ⋮ The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles ⋮ Improper C-colorings of graphs ⋮ A note on relaxed equitable coloring of graphs ⋮ The Alon-Tarsi number of a planar graph minus a matching ⋮ Decomposition of planar graphs with forbidden configurations ⋮ Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable ⋮ Defective 2-colorings of sparse graphs ⋮ Subcolorings and the subchromatic number of a graph ⋮ Some defective parameters in graphs ⋮ Improper colorability of planar graphs without prescribed short cycles ⋮ Monochromatic subgraphs in iterated triangulations ⋮ (1,k)-Coloring of Graphs with Girth at Least Five on a Surface ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes ⋮ Planar graphs with cycles of length neither 4 nor 6 are \((2,0,0)\)-colorable ⋮ Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph ⋮ A simple competitive graph coloring algorithm. II. ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests ⋮ \((1,0,0)\)-colorability of planar graphs without cycles of length 4, 5 or 9 ⋮ On 2-defective DP-colorings of sparse graphs ⋮ Defective DP-colorings of sparse multigraphs ⋮ On generalized choice and coloring numbers ⋮ Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1 ⋮ Planar graphs with girth at least 5 are \((3, 5)\)-colorable ⋮ On \(S\)-packing edge-colorings of cubic graphs ⋮ Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable ⋮ List strong linear 2-arboricity of sparse graphs ⋮ On improperly chromatic-choosable graphs ⋮ \((1,0,0)\)-colorability of planar graphs without prescribed short cycles ⋮ Co-2-plex vertex partitions ⋮ 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 ⋮ Defective 3-paintability of planar graphs ⋮ Improper colouring of (random) unit disk graphs ⋮ Sufficient conditions on planar graphs to have a relaxed DP-3-coloring
This page was built for publication: Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
