Every triangle-free planar graph has a planar upward drawing

A planar ordered set has a triangle-free, planar covering graph; on the other hand, there are nonplanar ordered sets whose covering graphs are planar. We show thatevery triangle-free planar graph has a planar upward drawing. This planar upward drawing can be constructed in time, polynomial in the number of vertices.Our results shed light on the apparently difficult problem, of long-standing, whether there is aneffective planarity-testing procedure for an ordered set.Supported in part by the Alexander von Humboldt Stiftung.Supported in part by the Deutsche Forschungsgemeinschaft.     

Every rayless graph has an unfriendly partition

It is proved that every graph containing no infinite path has an unfriendly partition.     

Every rayless graph has an unfriendly partition

We prove that every rayless graph has an unfriendly partition.     

Every monotone graph property has a sharp threshold

In their seminal work which initiated random graph theory Erdös and Rényi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This follows from the following theorem. Let denote the Hamming space endowed with the probability measure defined by , where . Let be a monotone subset of . We say that is symmetric if there is a transitive permutation group on such that is invariant under . Theorem. For every symmetric monotone , if then for . ( is an absolute constant.)

     

Every planar graph with the Liouville property is amenable

We introduce a strengthening of the notion of transience for planar maps in order to relax the standard condition of bounded degree appearing in various results, in particular, the existence of Dirichlet harmonic function s proved by Benjamini and Schramm. As a corollary we obtain that every planar nonamenable graph admits nonconstant Dirichlet harmonic function s27.     

Every graph occurs as an induced subgraph of some hypohamiltonian graph

We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for K₃, and Collier and Schmeichel, who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph.     

DP-3-coloring of some planar graphs

In this article, we use a unified approach to prove several classes of planar graphs are DP-3-colorable, which extend the corresponding results on 3-choosability.     

Every -CS-module has an indecomposable decomposition

We show that every -CS module is a direct sum of uniform modules, thus solving an open problem posed in 1994 by Dung, Huynh, Smith and Wisbauer. With the help of this result we also answer several other questions related to indecomposable decompositions of CS-modules.

     

2-Distance 4-coloring of planar subcubic graphs

The trivial lower bound for the 2-distance chromatic number χ ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 23, which strengthens a similar result by O. V. Borodin, A. O. Ivanova, and T. K. Neustroeva (2004) and Z. Dvořák, R. Škrekovski, and M. Tancer (2008) for g ≥ 24.     

A linear 5-coloring algorithm of planar graphs

A simple linear algorithm is presented for coloring planar graphs with at most five colors. The algorithm employs a recursive reduction of a graph involving the deletion of a vertex of degree 6 or less possibly together with the identification of its several neighbors.     

Every connected graph is a query graph

Let V be a set of bit strings of length k, i.e., V ? {0, 1}^k. The query graph Q(V) is defined as follows: the vertices of Q(V) are the elements of V, and {ū, v?} is an edge of Q(V) if and only if no other w? ? V agrees with ū in all the positions in which v? does. If V represents the set of keys for a statistical data base in which queries that match only one key are rejected, then the security of the individual data is related to the graph Q(V). Ernst Leiss showed that graphs belonging to any of several classes could be represented as query graphs and asked whether any connected graph could be so represented. We answer his question in the affirmative by making use of a spanning tree with special properties.     

Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable

Wang and Lih (2002) conjectured that every planar graph without adjacent triangles is 4-choosable. In this paper, we prove that every planar graph without any 4-cycle adjacent to two triangles is DP-4-colorable, which improves the results of Lam et al. (1999), Cheng et al. (2016) and Kim and Yu [ arXiv:1709.09809v1].     

Every planar graph without adjacent cycles of length at most 8 is 3-choosable

DP-coloring as a generalization of list coloring was introduced by Dvořák and Postle in 2017, who proved that every planar graph without cycles from 4 to 8 is 3-choosable, which was conjectured by Borodin et al. in 2007. In this paper, we prove that every planar graph without adjacent cycles of length at most 8 is 3-choosable, which extends this result of Dvořák and Postle.     

On the weak 2-coloring number of planar graphs

For a graph $G=(V,E)$, a total ordering L on V, and a vertex $v\in V$, let ${\mathrm{Wcol}}_2[G,L,v]$ be the set of vertices $w\in V$ for which there is a path from v to w whose length is 0, 1 or 2 and whose L-least vertex is w. The weak 2-coloring number ${\mathrm{wcol}}_2(G)$ of G is the least k such that there is a total ordering L on V with $|{\mathrm{Wcol}}_2[G,L,v]|\le k$ for all vertices $v\in V$. We improve the known upper bound on the weak 2-coloring number of planar graphs from 28 to 23. As the weak 2-coloring number is the best known upper bound on the star list chromatic number of planar graphs, this bound is also improved.     

Every signed planar graph without cycles of length from 4 to 8 is 3-colorable

In this paper, we investigate the signed graph version of Erdös problem: Is there a constant $c$ such that every signed planar graph without $k$-cycles, where $4\le k\le c$, is 3-colorable and prove that each signed planar graph without cycles of length from 4 to 8 is 3-colorable.     

On acyclic colorings of planar graphs

The conjecture of B. Grünbaum on existing of admissible vertex coloring of every planar graph with 5 colors, in which every bichromatic subgraph is acyclic, is proved and some corollaries of this result are discussed in the present paper.     

On acyclic colorings of planar graphs

The conjecture of B. Grünbaum on existing of admissible vertex coloring of every planar graph with 5 colors, in which every bichromatic subgraph is acyclic, is proved and some corollaries of this result are discussed in the present paper.