Buchumschlag

On the Structure of Hamiltonian Graphs with Small Independence Number

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Jedličková, Nikola, Kratochvíl, Jan
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Combinatorics Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
von: Bok, Jan, et al.
Veröffentlicht: (2021)

Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
von: Jedličková, Nikola, et al.
Veröffentlicht: (2023)

Computational complexity of covering regular trees
von: Bok, Jan, et al.
Veröffentlicht: (2025)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
von: Hsieh, Jun-Ting, et al.
Veröffentlicht: (2024)

Reinforced Generation of Combinatorial Structures: Ramsey Numbers
von: Nagda, Ansh, et al.
Veröffentlicht: (2026)

Computational Complexity of Covering Colored Mixed Multigraphs with Simple Degree Partitions
von: Bok, Jan, et al.
Veröffentlicht: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
von: Beisegel, Jesse, et al.
Veröffentlicht: (2025)

Constant Degree Direct Product Testers with Small Soundness
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

Improved Small Set Expansion in High Dimensional Expanders
von: Kaufman, Tali, et al.
Veröffentlicht: (2025)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
von: Li, Xin, et al.
Veröffentlicht: (2024)

Lions and Contamination: Trees and General Graphs
von: Kim, Dohoon, et al.
Veröffentlicht: (2026)

On a Hierarchy of Spectral Invariants for Graphs
von: Arvind, V., et al.
Veröffentlicht: (2023)

Direct Product Primality Testing of Graphs is GI-hard
von: Calderoni, Luca, et al.
Veröffentlicht: (2020)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2025)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
von: Baril, Ambroise, et al.
Veröffentlicht: (2024)

Finding a HIST: Chordality, Structural Parameters, and Diameter
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
von: Beisegel, Jesse, et al.
Veröffentlicht: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
von: Beisegel, Jesse, et al.
Veröffentlicht: (2025)

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
von: Cheng, Kuan, et al.
Veröffentlicht: (2026)

Reconfiguring Graph Homomorphisms on the Sphere
von: Lee, Jae-Baek, et al.
Veröffentlicht: (2018)

Determining the Outerthickness of Graphs Is NP-Hard
von: Lee, Pin-Hsian, et al.
Veröffentlicht: (2026)

Graph Irregularity via Edge Deletions
von: Bensmail, Julien, et al.
Veröffentlicht: (2025)

The Interplay Between Domination and Separation in Graphs
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2026)

Complexity Aspects of Homomorphisms of Ordered Graphs
von: Čertík, Michal, et al.
Veröffentlicht: (2025)

On Computational Aspects of Cores of Ordered Graphs
von: Čertík, Michal, et al.
Veröffentlicht: (2025)

Testing Isomorphism of Graphs in Polynomial Time
von: Xue, Rui
Veröffentlicht: (2023)

The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
von: Beisegel, Jesse, et al.
Veröffentlicht: (2024)

Hardness of 4-Colourings G-Colourable Graphs
von: Avvakumov, Sergey, et al.
Veröffentlicht: (2025)

Finding d-Cuts in Claw-free Graphs
von: Ahn, Jungho, et al.
Veröffentlicht: (2025)

On Detecting $H$-Induced Minors for Small $H$
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2026)

Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
von: Concha-Vega, Pablo
Veröffentlicht: (2026)

Finding Minimum Matching Cuts in $H$-free Graphs
von: Lucke, Felicia, et al.
Veröffentlicht: (2025)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
von: Mondada, Luca, et al.
Veröffentlicht: (2023)

Algorithmic methods of finite discrete structures. Graph clique problem
von: Kurapov, Sergey, et al.
Veröffentlicht: (2024)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
von: Lucke, Felicia
Veröffentlicht: (2025)

Structural Origins of Cubic Complexity in Pebble Motion
von: Nakamigawa, Tomoki, et al.
Veröffentlicht: (2025)

Low-Degree Polynomials Are Good Extractors
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
von: Basu, Arpon, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)