We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, ...we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.
For a class
D of drawings of loopless (multi‐)graphs in the plane, a drawing
D
∈
D is saturated when the addition of any edge to
D results in
D
′
∉
D—this is analogous to saturated graphs in a graph ...class as introduced by Turán and Erdős, Hajnal, and Moon. We focus on
k‐planar drawings, that is, graphs drawn in the plane where each edge is crossed at most
k times, and the classes
D of all
k‐planar drawings obeying a number of restrictions, such as having no crossing incident edges, no pair of edges crossing more than once, or no edge crossing itself. While saturated
k‐planar drawings are the focus of several prior works, tight bounds on how sparse these can be are not well understood. We establish a generic framework to determine the minimum number of edges among all
n‐vertex saturated
k‐planar drawings in many natural classes. For example, when incident crossings, multicrossings and selfcrossings are all allowed, the sparsest
n‐vertex saturated
k‐planar drawings have
2
k
−
(
k
mod
2
)
(
n
−
1
) edges for any
k
≥
4, while if all that is forbidden, the sparsest such drawings have
2
(
k
+
1
)
k
(
k
−
1
)
(
n
−
1
) edges for any
k
≥
6.
We introduce the family of k-gap-planar graphs for k≥0, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its ...crossings. This definition is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.
The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree Δ≥3 that is not the complete graph KΔ+1 or the complete bipartite graph KΔ,Δ admits an equitable coloring with Δ ...colors. For planar graphs, the conjecture has been confirmed for Δ≥13 by Yap and Zhang and for 9≤Δ≤12 by Nakprasit. In this paper, we present a proof that confirms the conjecture for graphs embeddable into a surface with non-negative Euler characteristic with maximum degree Δ≥9 and for planar graphs with maximum degree Δ≥8.
A graph G is (d1,d2)-colorable if its vertices can be partitioned into two subsets V1 and V2 such that Δ(GV1)≤d1 and Δ(GV2)≤d2. Let G5 denote the family of planar graphs with girth at least 5. In ...this paper, we prove that every graph in G5 without adjacent 5-cycles is (1,6)-colorable.
•This is a new result towards planar graphs with girth 5 and containing no adjacent 5-cycles.•The skill of discharging method in this paper is a powerful tool to solve the problem of this kind of coloring.•The discharging rulers are well designed.•Establish some reducible configurations by using clever skills.
PDF
