Planar graphs without 4-cycles and close triangles are (2,0,0)-colorable

DOI10.1007/S10878-018-0298-2zbMATH Open1393.05088arXiv1806.07511OpenAlexW2802381718MaRDI QIDQ721920FDOQ721920

Gexin Yu, Runrun Liu, Jennifer Vandenbussche, Heather Hoskins

Publication date: 20 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: For a set of nonnegative integers $c_1,ldots,c_k$, a $(c_1,c_2,ldots,c_k)$-coloring of a graph $G$ is a partition of $V(G)$ into $V_1,ldots,V_k$ such that for every $i$, $1leilek,G[V_i]$ has maximum degree at most $c_i$. We prove that all planar graphs without 4-cycles and no less than two edges between triangles are $(2,0,0)$-colorable.

Full work available at URL: https://arxiv.org/abs/1806.07511

zbMATH Keywords

planar graphsdischarging3-colorable graph

Mathematics Subject Classification ID

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

Cites Work

• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Improper Choosability of Planar Graphs without 4-Cycles
• Three-coloring triangle-free graphs on surfaces. I: Extending a coloring to a disk with one triangle.
• Title not available (Why is that?)
• On a conjecture of B. Grünbaum
• On $(3,1)^*$-Coloring of Plane Graphs
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Steinberg's conjecture is false
• Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
• Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable
• Near-colorings: non-colorable graphs and NP-completeness
• Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
• A Relaxation of Steinberg's Conjecture
• A relaxation of the Bordeaux conjecture
• A relaxation of the strong Bordeaux Conjecture
• 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

Cited In (4)

• The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
• Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable
• Planar graphs without cycles of length 4 or 9 are $\boldsymbol{(2,~0,~0)}$-colorable
• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable

This page was built for publication: Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable

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