Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Inoue, Yuta, Kawarabayashi, Ken-ichi, Miyashita, Atsuyuki, Mohar, Bojan, Thomassen, Carsten, Thorup, Mikkel
Formato:	Preprint
Publicado:	2026
Materias:	Combinatorics Computational Geometry Discrete Mathematics Data Structures and Algorithms 05 E.1
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem
por: Inoue, Yuta, et al.
Publicado: (2024)

Online Graph Coloring for $k$-Colorable Graphs
por: Kawarabayashi, Ken-ichi, et al.
Publicado: (2025)

EPTAS for Hard Graph Cut Problems for Dense Graphs
por: Deguchi, Kaisei, et al.
Publicado: (2026)

Better coloring of 3-colorable graphs
por: Kawarabayashi, Ken-ichi, et al.
Publicado: (2024)

Online Coloring of Short Intervals
por: Chybowska-Sokół, Joanna, et al.
Publicado: (2018)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
por: Ghanbari, Babak, et al.
Publicado: (2026)

On The Maximum Linear Arrangement Problem for Trees
por: Alemany-Puig, Lluís, et al.
Publicado: (2023)

5-Coloring Planar Graphs with a Color Class of Order at Most $|V|/6$
por: Inoue, Yuta, et al.
Publicado: (2025)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
por: Paschalidis, Phevos, et al.
Publicado: (2023)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
por: Bourneuf, Romain, et al.
Publicado: (2025)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
por: Hellmuth, Marc, et al.
Publicado: (2023)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
por: Dudeja, Aditi, et al.
Publicado: (2024)

Induced Cycles of Many Lengths
por: Chudnovsky, Maria, et al.
Publicado: (2026)

On the sizes of BDDs and ZDDs representing matroids
por: Emoto, Hiromi, et al.
Publicado: (2024)

An Alternate Proof of Near-Optimal Light Spanners
por: Bodwin, Greg
Publicado: (2023)

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
por: Jenssen, Matthew, et al.
Publicado: (2023)

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
por: Chakrabarty, Deeparnab, et al.
Publicado: (2024)

The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability
por: Feghali, Carl, et al.
Publicado: (2025)

Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture
por: Inoue, Yuta, et al.
Publicado: (2025)

Color-Constrained Arborescences in Edge-Colored Digraphs
por: Ardra, P. S., et al.
Publicado: (2025)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
por: Dhawan, Abhishek
Publicado: (2024)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
por: Paul-Pena, Daniel, et al.
Publicado: (2022)

Exponential Time Approximation for Coloring 3-Colorable Graphs
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
por: Bencs, Ferenc, et al.
Publicado: (2024)

The Strong Birthday Problem Revisited
por: Tripathy, Chijul B.
Publicado: (2025)

Reconfiguration of List Colourings
por: Cambie, Stijn, et al.
Publicado: (2025)

Parameterized complexity of isometric path partition: treewidth and diameter
por: Chakraborty, Dibyayan, et al.
Publicado: (2025)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
por: Ghanbari, Babak, et al.
Publicado: (2025)

On the Enumeration of all Unique Paths of Recombining Trinomial Trees
por: Torres, Ethan, et al.
Publicado: (2025)

Vigemers: on the number of $k$-mers sharing the same XOR-based minimizer
por: Ingels, Florian, et al.
Publicado: (2026)

Approximating maximum-size properly colored forests
por: Bai, Yuhang, et al.
Publicado: (2024)

Problems on Group-labeled Matroid Bases
por: Hörsch, Florian, et al.
Publicado: (2024)

$α_i$-Metric Graphs: Hyperbolicity
por: Dragan, Feodor F., et al.
Publicado: (2024)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
por: Deák, Bence, et al.
Publicado: (2026)

Rainbow Arborescence Conjecture
por: Bérczi, Kristóf, et al.
Publicado: (2024)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
por: An, Shinwoo, et al.
Publicado: (2025)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
por: Holtgrefe, Niels, et al.
Publicado: (2024)

Unsplittable Transshipments
por: Debgupta, Srinwanti, et al.
Publicado: (2026)

Cuts in Graphs with Matroid Constraints
por: Banik, Aritra, et al.
Publicado: (2024)

Optimal and Efficient Partite Decompositions of Hypergraphs
por: Krapivin, Andrew, et al.
Publicado: (2025)