Image de couverture de livre

Better coloring of 3-colorable graphs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kawarabayashi, Ken-ichi, Thorup, Mikkel, Yoneda, Hirotaka
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms Combinatorics G.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
par: Jędrzejczak, Patryk, et autres
Publié: (2025)

Optimal distance query reconstruction for graphs without long induced cycles
par: Bastide, Paul, et autres
Publié: (2023)

Lower Bounds for Leaf Rank of Leaf Powers
par: Høgemo, Svein
Publié: (2024)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
par: Bourneuf, Romain, et autres
Publié: (2025)

Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
par: Ma, Will, et autres
Publié: (2024)

Online Bipartite Matching in the Probe-Commit Model
par: Borodin, Allan, et autres
Publié: (2023)

Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry
par: Mukherjee, Sayan, et autres
Publié: (2025)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
par: MacRury, Calum, et autres
Publié: (2022)

Online Graph Coloring for $k$-Colorable Graphs
par: Kawarabayashi, Ken-ichi, et autres
Publié: (2025)

Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph
par: Bhandari, Kritika, et autres
Publié: (2025)

Weisfeiler-Leman on graphs of small twin-width
par: Heinrich, Irene, et autres
Publié: (2026)

SSD Set System, Graph Decomposition and Hamiltonian Cycle
par: Shota, Kan, et autres
Publié: (2024)

Structural and Combinatorial Properties of 2-swap Word Permutation Graphs
par: Adamson, Duncan, et autres
Publié: (2023)

Low-degree spanning trees of $2$-edge-connected graphs in linear time
par: Dereniowski, Dariusz, et autres
Publié: (2024)

Color-Constrained Arborescences in Edge-Colored Digraphs
par: Ardra, P. S., et autres
Publié: (2025)

Computing parameters that generalize interval graphs using restricted modular partitions
par: Bonomo-Braberman, Flavia, et autres
Publié: (2025)

Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees
par: Høgemo, Svein
Publié: (2024)

Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
par: Kaudan, Chirag, et autres
Publié: (2026)

Engineering Algorithms for $\ell$-Isolated Maximal Clique Enumeration
par: D'Elia, Marco, et autres
Publié: (2025)

Approximating the Average-Case Graph Search Problem with Non-Uniform Costs
par: Szyfelbein, Michał
Publié: (2025)

Speeding-up Graph Algorithms via Clique Partitioning
par: Chavan, Akshar, et autres
Publié: (2025)

An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors
par: De Meyer, Lucas, et autres
Publié: (2025)

Realizing temporal graphs from fastest travel times
par: Klobas, Nina, et autres
Publié: (2023)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
par: Bougeret, Marin, et autres
Publié: (2024)

Kernelization dichotomies for hitting minors under structural parameterizations
par: Bougeret, Marin, et autres
Publié: (2025)

Online coloring of short interval graphs and two-count interval graphs
par: Curbelo, Israel R.
Publié: (2024)

A polynomial-time algorithm for recognizing high-bandwidth graphs
par: Varona, Luis M. B.
Publié: (2026)

Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems
par: Könen, David, et autres
Publié: (2023)

Flip-width: Cops and Robber on dense graphs
par: Toruńczyk, Szymon
Publié: (2023)

Minimum-cost paths for electric cars
par: Dorfman, Dani, et autres
Publié: (2024)

Fast and Simple Sorting Using Partial Information
par: Haeupler, Bernhard, et autres
Publié: (2024)

Bidirectional Dijkstra's Algorithm is Instance-Optimal
par: Haeupler, Bernhard, et autres
Publié: (2024)

Structural Parameterization of Steiner Tree Packing
par: Hastrich, Niko, et autres
Publié: (2025)

JFR: An Efficient Jump Frontier Relaxation Strategy for Bellman-Ford
par: Wang, Xin, et autres
Publié: (2025)

Customizable Contraction Hierarchies -- A Survey
par: Bläsius, Thomas, et autres
Publié: (2025)

Maintaining Routing Structures under Deletions via Self-Pruning
par: Haeupler, Bernhard, et autres
Publié: (2025)

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
par: Haeupler, Bernhard, et autres
Publié: (2023)

Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
par: Balzotti, Lorenzo
Publié: (2020)

Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity
par: Dreier, Jan, et autres
Publié: (2026)

Faster shortest-path algorithms using the acyclic-connected tree
par: Stefansson, Elis, et autres
Publié: (2025)