B. Mohar

Three-edge-coloring apex cubic graphs

Yuta Inoue, Ken-ichi Kawarabayashi, Rintaro Matsuo +3

A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G - v$ is planar. We prove that every $2$ -connected apex cubic graph is three-edge-colorable. This result gives the fina…

The Dominating 4-Colour Theorem

António Girão, Freddie Illingworth, Bojan Mohar +6

A "dominating $K_{t}$ -model" in a graph $G$ is a sequence $(T_{1}, \dots, T_{t})$ of pairwise vertex-disjoint connected subgraphs of $G$ , such that whenever $1 \leq i < j \leq t$ every vertex…

The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +3

We give a near-linear time 4-coloring algorithm for planar graphs, improving on the previous quadratic time algorithm by Robertson et al. from 1996. Such an algorithm cannot be ach…

Long cycles in vertex transitive digraphs

Matija Bucić, Kevin Hendrey, Bojan Mohar +2

One of the most well-known conjectures concerning Hamiltonicity in graphs asserts that any sufficiently large connected vertex transitive graph contains a Hamilton cycle. In this f…

Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +2

We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the torus, with the exceptional graph class called "Petersen-like", is 3-edge-colorable. This me…

On a conjecture concerning 4-coloring of graphs with one crossing

Zdeněk Dvořák, Bernard Lidický, Bojan Mohar

We conjecture that every graph of minimum degree five with no separating triangles and drawn in the plane with one crossing is 4-colorable. In this paper, we use computer enumerati…

Vertex Partitioning and $p$ -Energy of Graphs

Saieed Akbari, Hitesh Kumar, Bojan Mohar +1

For a Hermitian matrix $A$ of order $n$ with eigenvalues $λ_{1} (A) \geq \dots \geq λ_{n} (A)$ , define \[ \mathcal{E}_p^+(A)=\sum_{λ_i > 0} λ_i^p(A), \quad \mathcal{E}_p^-(A)=\sum_{λ_i<0} |…

Hermitian adjacency matrices with at most three distinct eigenvalues

Saieed Akbari, Jonathan Aloni, Maxwell Levit +2

We study oriented graphs whose Hermitian adjacency matrices of the second kind have few eigenvalues. We give a complete characterization of the oriented graphs with two distinct ei…

A Linear Lower Bound for the Square Energy of Graphs

Saieed Akbari, Hitesh Kumar, Bojan Mohar +1

Let $G$ be a graph of order $n$ with eigenvalues $λ_{1} \geq \dots \geq λ_{n}$ . Let \[s^+(G)=\sum_{λ_i>0} λ_i^2, \qquad s^-(G)=\sum_{λ_i<0} λ_i^2.\] The smaller value, $s(G)=\min\{s^+(…

Bipartite graphs are $(\frac{4}{5} - ε) \frac{Δ}{l o g Δ}$ -choosable

Peter Bradshaw, Bojan Mohar, Ladislav Stacho

Alon and Krivelevich conjectured that if $G$ is a bipartite graph of maximum degree $Δ$ , then the choosability (or list chromatic number) of $G$ satisfies $χ_{\ell}(G) = O \left (…

Clustered Colouring of Graph Products

Rutger Campbell, J. Pascal Gollin, Kevin Hendrey +5

A colouring of a graph $G$ has clustering $k$ if the maximum number of vertices in a monochromatic component equals $k$ . Motivated by recent results showing that many natural graph…

Guarding isometric subgraphs and Cops and Robber in planar graphs

Sebastián González Hermosillo de la Maza, Bojan Mohar

In the game of Cops and Robbers, one of the most useful results is that an isometric path in a graph can be guarded by one cop. In this paper, we introduce the concept of wide shad…

Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +2

We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In o…

Sharing tea on a graph

J. Pascal Gollin, Kevin Hendrey, Hao Huang +6

Motivated by the analysis of consensus formation in the Deffuant model for social interaction, we consider the following procedure on a graph $G$ . Initially, there is one unit of t…

Strong log-convexity of genus sequences

Bojan Mohar

For a graph $G$ , and a nonnegative integer $g$ , let $a_{g} (G)$ be the number of $2$ -cell embeddings of $G$ in an orientable surface of genus $g$ (counted up to the combinatorial home…

Cops and Robber on Hyperbolic Manifolds

Vesna Iršič, Bojan Mohar, Alexandra Wesolek

The Cops and Robber game on geodesic spaces is a pursuit-evasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pu…

math.CO2023

Subdivision and Graph Eigenvalues

Hitesh Kumar, Bojan Mohar, Shivaramakrishna Pragada +1

This paper investigates the asymptotic nature of graph spectra when some edges of a graph are subdivided sufficiently many times. In the special case where all edges of a graph are…

math.CO2022★ 2 cited

Treewidth, Circle Graphs and Circular Drawings

Robert Hickingbotham, Freddie Illingworth, Bojan Mohar +1

A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples…

Genus Polynomials of Cubic Graphs with Non-Real Roots

MacKenzie Carr, Varpreet Dhaliwal, Bojan Mohar

Given a graph $G$ , its genus polynomial is $Γ_{G} (x) = \sum_{k \geq 0} g_{k} (G) x^{k}$ , where $g_{k} (G)$ is the number of 2-cell embeddings of $G$ in an orientable surface of genus $k$ . The…

math.CO2022★ 2 cited

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic

Jesse Campion Loth, Kevin Halasz, Tomáš Masařík +2

A random 2-cell embedding of a connected graph $G$ in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of fa…

Graphs of Linear Growth have Bounded Treewidth

Rutger Campbell, Marc Distel, J. Pascal Gollin +5

A graph class $G$ has linear growth if, for each graph $G \in G$ and every positive integer $r$ , every subgraph of $G$ with radius at most $r$ contains $O (r)$ v…

math.CO2022★ 2 cited

List-avoiding orientations

Peter Bradshaw, Yaobin Chen, Hao Ma +2

Given a graph $G$ with a set $F (v)$ of forbidden values at each $v \in V (G)$ , an $F$ -avoiding orientation of $G$ is an orientation in which $d e g^{+} (v) \neq \in F (v)$ for each vertex…

On density of $Z_{3}$ -flow-critical graphs

Zdeněk Dvořák, Bojan Mohar

For an abelian group $Γ$ , a graph $G$ is said to be $Γ$ -flow-critical if $G$ does not admit a nowhere-zero $Γ$ -flow, but for each edge $e \in E (G)$ , the contraction $G / e$ has a nowh…