Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

DOI10.1002/(SICI)1097-0118(199602)21:2%3C183::AID-JGT7%3E3.0.CO;2-NMaRDI QIDQ4865526zbMATH OpenOpenAlexFDO

Authors Oleg V. Borodin

Publication date 25 February 1996

Full work available at URL https://doi.org/10.1002/(sici)1097-0118(199602)21:2%3C183::aid-jgt7%3E3.0.co;2-n

zbMATH Keywords

3-coloringplane graphtriangles

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• Planar graphs without adjacent cycles of length at most seven are 3-colorable
• Planar graphs without cycles of length from 4 to 7 are 3-colorable

Cited in

(68)

• (\(1,1,0\))-coloring of planar graphs without cycles of length 4 and 6
• On 3-colorable planar graphs without prescribed cycles
• A note on 3-choosability of planar graphs
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
• A note on 3-choosability of planar graphs without certain cycles
• Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable
• The 4-choosability of plane graphs without 4-cycles
• Triangles with restricted degree sum of their boundary vertices in plane graphs
• A condition for the three colourability of planar locally path graphs
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
• Every toroidal graph without adjacent triangles is \((4,1)^{*}\)-choosable
• On doubly light triangles in plane graphs
• Three coloring via triangle counting
• A note on list improper coloring planar graphs
• Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable
• A note on the acyclic 3-choosability of some planar graphs
• Acyclic 4-choosability of planar graphs with no 4- and 5-cycles
• Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
• Facially-constrained colorings of plane graphs: a survey
• On structure of some plane graphs with application to choosability
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• A Steinberg-like approach to describing faces in 3-polytopes
• Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
• Plane Triangulations Without a Spanning Halin Subgraph: Counterexamples to the Lovász--Plummer Conjecture on Halin Graphs
• Circular coloring and fractional coloring in planar graphs
• Total colorings of planar graphs without adjacent triangles
• Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable
• The 3-colorability of planar graphs without cycles of length 4, 6 and 9
• A note on the three color problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles
• Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable
• A sufficient condition on 3-colorable plane graphs without 5- and 6-circuits
• Light 3-faces in 3-polytopes without adjacent triangles
• Three-coloring planar graphs without short cycles
• Steinberg's conjecture is false
• On 3-colorability of planar graphs without adjacent short cycles
• Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles
• On 3-colorings of plane graphs
• A note on the not 3-choosability of some families of planar graphs
• On 3-colorable planar graphs without short cycles
• On the 3-colorability of planar graphs without 4-, 7- and 9-cycles
• An analogue of DP-coloring for variable degeneracy and its applications
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• The surviving rate of planar graphs without short cycles
• Every signed planar graph without cycles of length from 4 to 8 is 3-colorable
• A non-3-choosable planar graph without cycles of length 4 and 5
• Distance constraints on short cycles for 3-colorability of planar graphs
• On 3-choosability of plane graphs without 6-, 7- and 9-cycles
• A step towards the strong version of Havel's three color conjecture
• A structural theorem on embedded graphs and its application to colorings
• Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable
• Acyclic choosability of planar graphs: a Steinberg like approach
• Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable
• \((1,0,0)\)-colorability of planar graphs without cycles of length \(4\) or \(6\)
• A note on 3-choosability of plane graphs under distance restrictions
• Some structural properties of planar graphs and their applications to 3-choosability
• An introduction to the discharging method via graph coloring
• List coloring of planar graphs with forbidden cycles
• A relaxation of Havel's 3-color problem
• Planar graphs without adjacent cycles of length at most seven are 3-colorable
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• \((1,0,0)\)-colorability of planar graphs without cycles of length 4, 5 or 9
• Equitable and list equitable colorings of planar graphs without 4-cycles
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• On 3-colorable planar graphs without cycles of four lengths
• A 3-color theorem on plane graphs without 5-circuits

This page was built for publication: Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4865526)