The (3, 3)-colorability of planar graphs without 4-cycles and 5-cycles
From MaRDI portal
Publication:2685340
Recommendations
- Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
- Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
- Planar graphs without cycles of length 4 or 5 are (2, 0, 0)-colorable
- Planar graphs without cycles of length 4 or 9 are $\boldsymbol{(2,~0,~0)}$-colorable
- A relaxation of Steinberg's conjecture
Cites work
- (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
- An introduction to the discharging method via graph coloring
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
- Defective 2-colorings of sparse graphs
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
- Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable
- Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable
- scientific article; zbMATH DE number 434910 (Why is no real title available?)
- Improper choosability of graphs and maximum average degree
- Near-colorings: non-colorable graphs and NP-completeness
- Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
- Planar graphs with girth at least 5 are \((3, 4)\)-colorable
- Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
- Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
- Planar graphs without cycles of length 4 or 5 are (2, 0, 0)-colorable
- Steinberg's conjecture is false
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
Cited in
(32)- Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
- Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
- Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable
- New restrictions on defective coloring with applications to Steinberg-type graphs
- Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
- Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph
- Every planar graph without 5-cycles and \(K_4^-\) and adjacent 4-cycles is \((2, 0, 0)\)-colorable
- Planar graphs without cycles of length 4 or 5 are (11 : 3)-colorable
- On 3-colorable planar graphs without cycles of four lengths
- On the 3-colorability of planar graphs without \(\{4,8,9\}\)-cycles
- Three-colourability of planar graphs with no 5- or triangular \(\{3,6\}\)-cycles
- Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
- scientific article; zbMATH DE number 7029178 (Why is no real title available?)
- scientific article; zbMATH DE number 1882353 (Why is no real title available?)
- The 3-colorability of planar graphs without cycles of length 4, 6 and 9
- A relaxation of Steinberg's conjecture
- Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable
- A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
- Cycle adjacency of planar graphs and 3-colourability
- Planar graphs without 4- and 6-cycles are \(( 3 , 4 )\)-colorable
- Partitioning planar graphs into bounded degree forests
- Partitioning planar graphs without 4-cycles and 6-cycles into two disjoint subcubic forests
- \((\mathcal{F}_1, \mathcal{F})\)-partition of plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles
- An \((\mathcal{F}_2, \mathcal{F}_6)\)-partition of planar graphs without cycles of length 4 and 6
- An \((\mathcal{F}_3, \mathcal{F}_4)\)-partition of planar graphs without 4- and 6-cycles
- The independence ratio of 4-cycle-free planar graphs
- Every planar graph without 4- and 6-cycles is (2,5)-colorable
- On partitioning a planar graph into two forests of maximum degree at most three
- On \((\mathscr{F, F}_2)\)-partitionability of planar graphs without \(\{4,7\}\)-cycles
- A counterexample to the conjecture of Aksionov and Mel'nikov on non-3- colorable planar graphs
- Three-coloring planar graphs without short cycles
- On 3-colorable plane graphs without 5- and 7-cycles
This page was built for publication: The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2685340)
