Copertina

Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Jedličková, Nikola, Kratochvíl, Jan
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Discrete Mathematics Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Computational complexity of covering regular trees
di: Bok, Jan, et al.
Pubblicazione: (2025)

Computational Complexity of Covering Colored Mixed Multigraphs with Simple Degree Partitions
di: Bok, Jan, et al.
Pubblicazione: (2025)

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
di: Bok, Jan, et al.
Pubblicazione: (2021)

List homomorphisms to separable signed graphs
di: Bok, Jan, et al.
Pubblicazione: (2023)

On the expressive power of $2$-edge-colourings of graphs
di: Bok, Jan, et al.
Pubblicazione: (2025)

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths
di: Baste, Julien, et al.
Pubblicazione: (2025)

Immersions of large cliques in graphs with independence number 2 and bounded maximum degree
di: Botler, Fábio, et al.
Pubblicazione: (2025)

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
di: Bok, Jan, et al.
Pubblicazione: (2020)

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
di: Pilipczuk, Marcin, et al.
Pubblicazione: (2023)

Algorithmic methods of finite discrete structures. Hamiltonian cycle of a complete graph and the Traveling salesman problem
di: Kurapov, Sergey, et al.
Pubblicazione: (2024)

Hamiltonian connectivity of some base-cobase graphs
di: Martínez-Sandoval, Leonardo, et al.
Pubblicazione: (2025)

Biclique immersions in graphs with independence number 2
di: Botler, Fábio, et al.
Pubblicazione: (2023)

On the Structure of Hamiltonian Graphs with Small Independence Number
di: Jedličková, Nikola, et al.
Pubblicazione: (2024)

Bounded twin-width graphs are polynomially $χ$-bounded
di: Bourneuf, Romain, et al.
Pubblicazione: (2023)

Tree-independence number of $P_5$-free graphs with no large bicliques
di: Blažej, Václav, et al.
Pubblicazione: (2026)

Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
di: Kelly, Tom, et al.
Pubblicazione: (2018)

Cops and robber in graphs with bounded vertex cover number
di: Bose, Prosenjit, et al.
Pubblicazione: (2026)

A quasi-optimal upper bound for induced paths in sparse graphs
di: Couëtoux, Basile, et al.
Pubblicazione: (2025)

Exact rainbow numbers of cycle-related graphs in multi-hubbed wheels
di: Dai, Mengyao, et al.
Pubblicazione: (2025)

EPPA numbers of graphs
di: Bradley-Williams, David, et al.
Pubblicazione: (2023)

Distance-based (and path-based) covering problems for graphs of given cyclomatic number
di: Chakraborty, Dibyayan, et al.
Pubblicazione: (2025)

On $(n,m)$-chromatic numbers of graphs having bounded sparsity parameters
di: Das, Sandip, et al.
Pubblicazione: (2023)

Polynomial-time recognition and maximum independent set in Burling graphs
di: Rzążewski, Paweł, et al.
Pubblicazione: (2024)

Clustered independence and bounded treewidth
di: Knauer, Kolja, et al.
Pubblicazione: (2023)

Two Proofs of the Hamiltonian Cycle Identity
di: Sawczuk, Hamilton, et al.
Pubblicazione: (2025)

The Frank number and nowhere-zero flows on graphs
di: Goedgebeur, Jan, et al.
Pubblicazione: (2023)

Upper bounds on the average number of colors in the non-equivalent colorings of a graph
di: Hertz, Alain, et al.
Pubblicazione: (2021)

Efficient polynomial-time approximation scheme for the genus of dense graphs
di: Jing, Yifan, et al.
Pubblicazione: (2020)

On the existence of factors intersecting sets of cycles in regular graphs
di: Goedgebeur, Jan, et al.
Pubblicazione: (2024)

On graphs coverable by chubby shortest paths
di: Hatzel, Meike, et al.
Pubblicazione: (2025)

Ramsey Goodness of paths and unbalanced graphs
di: Botler, Fábio, et al.
Pubblicazione: (2024)

Long induced paths in sparse graphs and graphs with forbidden patterns
di: Duron, Julien, et al.
Pubblicazione: (2024)

Planar cycle-extendable graphs
di: Dalwadi, Aditya Y, et al.
Pubblicazione: (2024)

Improved lower bounds on the maximum size of graphs with girth 5
di: Goedgebeur, Jan, et al.
Pubblicazione: (2025)

Bipartite Turán number of paths and other trees
di: Bonamy, Marthe, et al.
Pubblicazione: (2025)

Nucleation-free independent graphs with implied nonedges
di: Cheng, Jialong, et al.
Pubblicazione: (2025)

Making Walks Count: From Silent Circles to Hamiltonian Cycles
di: Alekseyev, Max A., et al.
Pubblicazione: (2016)

Induced matching treewidth and tree-independence number, revisited
di: Alon, Noga, et al.
Pubblicazione: (2025)

Hitting all longest paths in $H$-free graphs and $H$-graphs
di: de Lima, Paloma T., et al.
Pubblicazione: (2025)

Tight bound on treedepth in terms of pathwidth and longest path
di: Hatzel, Meike, et al.
Pubblicazione: (2023)