Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
A graph \(G\) is \((d_1, d_2, \ldots, d_k)\)-colorable if the vertex set of \(G\) can be partitioned into subsets \(V_1, V_2, \ldots , V_k\) such that the subgraph \(G[V_i ]\) induced by \(V_i\) has maximum degree at most \(d_i\) for \(i \in \{ 1, \ldots , k\}\). \textit{C. Zhang} et al. [Discrete Math. 339, No. 12, 3032--3042 (2016; Zbl 1343.05054)] asked whether every planar graph without adjacent cycles of length at most 5 is (1, 0, 0)-colorable. \textit{M. Chen} et al. [ibid. 339, No. 2, 886--905 (2016; Zbl 1327.05073)] approximated this conjecture by proving that every planar graph without cycles of length 4 and 5 is (2, 0, 0)-colorable. The authors improve this result by proving that every planar graph without adjacent cycles of length at most five is (2, 0, 0)-colorable.
- Planar graphs without adjacent cycles of length at most five are (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 5 are (3,0,0)-colorable
- Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
- Every planar graph without 5-cycles and \(K_4^-\) and adjacent 4-cycles is \((2, 0, 0)\)-colorable
- 2-distance coloring of planar graphs without adjacent 5-cycles
- Planar graphs without cycles of length 4 or 7 are (2, 0, 0)-colorable
- 1-planar graphs without 4-cycles or 5-cycles are 5-colorable
- Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
- Every 1-planar graph without cycles of length 3 or 4 is 5-colorable
- A relaxation of the Bordeaux conjecture
- A sufficient condition for planar graphs to be 3-colorable
- scientific article; zbMATH DE number 434910 (Why is no real title available?)
- Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable
- Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
- Planar graphs without adjacent cycles of length at most seven are 3-colorable
- Planar graphs without cycles of length 4 or 5 are (2, 0, 0)-colorable
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
- Steinberg's conjecture is false
- Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
- Planar graphs without chordal 5-cycles are 2-good
- A relaxation of Novosibirsk 3-color conjecture
- Every planar graph without 5-cycles and \(K_4^-\) and adjacent 4-cycles is \((2, 0, 0)\)-colorable
- The independence ratio of 4-cycle-free planar graphs
- Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
This page was built for publication: Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2021579)
