31 citations · 298 across the 114 of their papers we have counts for
137 papers
Three-edge-coloring apex cubic graphs
Yuta Inoue, Ken-ichi Kawarabayashi, Rintaro Matsuo +3
A graph is \emph{apex} if has a vertex such that is planar. We prove that every -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 -model" in a graph is a sequence of pairwise vertex-disjoint connected subgraphs of , such that whenever 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…