Imagen de Portada

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Hodur, Nadzieja, Pilśniak, Monika, Prorok, Magdalena, Rzążewski, Paweł
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity Combinatorics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On $k$-colorability of $(bull, H)$-free graphs
por: Hodur, Nadzieja, et al.
Publicado: (2025)

On 3-colourability of $(bull, H)$-free graphs
por: Hodur, Nadzieja, et al.
Publicado: (2024)

On 3-colorability of (claw, diamond)-free graphs
por: Hodur, Nadzieja, et al.
Publicado: (2026)

List coloring ordered graphs with forbidden induced subgraphs
por: Piecyk, Marta, et al.
Publicado: (2025)

$C_{2k+1}$-coloring of bounded-diameter graphs
por: Piecyk, Marta
Publicado: (2024)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
por: Ahn, Jungho, et al.
Publicado: (2022)

On Computational Aspects of Ordered Matching Problems
por: Čertík, Michal, et al.
Publicado: (2025)

Complexity Aspects of Homomorphisms of Ordered Graphs
por: Čertík, Michal, et al.
Publicado: (2025)

On Computational Aspects of Cores of Ordered Graphs
por: Čertík, Michal, et al.
Publicado: (2025)

Finding d-Cuts in Claw-free Graphs
por: Ahn, Jungho, et al.
Publicado: (2025)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
por: Chudnovsky, Maria, et al.
Publicado: (2024)

Finding Minimum Matching Cuts in $H$-free Graphs
por: Lucke, Felicia, et al.
Publicado: (2025)

Between proper and square coloring of planar graphs, hardness and extremal graphs
por: Delépine, Thomas
Publicado: (2026)

Structure of (bull, diamond)-free graphs and its applications
por: Mishra, Suchismita
Publicado: (2021)

Structural description of (bull, house)-free graphs
por: Belavadi, Manoj, et al.
Publicado: (2026)

On the finiteness of $k$-vertex-critical $2P_2$-free graphs with forbidden induced squids or bulls
por: Adekanye, Melvin, et al.
Publicado: (2024)

Distinguishing symmetric digraphs by proper arc-colourings of type I
por: Kalinowski, Rafał, et al.
Publicado: (2025)

A note on edge colorings distinguishing all triangles in a graph
por: Pilsniak, Monika, et al.
Publicado: (2024)

Clique-Width: Harnessing the Power of Atoms
por: Dabrowski, Konrad K., et al.
Publicado: (2020)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
por: Lokshtanov, Daniel, et al.
Publicado: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
por: Bhangale, Amey, et al.
Publicado: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
por: Bhangale, Amey, et al.
Publicado: (2024)

On Approximability of Satisfiable k-CSPs: IV
por: Bhangale, Amey, et al.
Publicado: (2023)

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
por: Le, Hoang-Oanh, et al.
Publicado: (2024)

Finding a HIST: Chordality, Structural Parameters, and Diameter
por: Hanaka, Tesshu, et al.
Publicado: (2025)

Sensitivity and Hamming graphs
por: Asensio, Sara, et al.
Publicado: (2025)

There are finitely many $5$-vertex-critical $(P_6,\text{bull})$-free graphs
por: Ju, Yiao, et al.
Publicado: (2025)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2025)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
por: Galby, Esther, et al.
Publicado: (2025)

Perfect divisibility of some bull-free graphs and its application
por: Chen, Ran, et al.
Publicado: (2026)

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

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
por: Le, Hoang-Oanh, et al.
Publicado: (2023)

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

HNN extensions of free groups with equal associated subgroups of finite index: polynomial time word problem
por: Shen, Hanwen, et al.
Publicado: (2025)

On graphs coverable by k shortest paths
por: Dumas, Maël, et al.
Publicado: (2022)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
por: Gan, Luyining, et al.
Publicado: (2023)

Restricted CSPs and F-free Digraph Algorithmics
por: Guzmán-Pro, Santiago, et al.
Publicado: (2025)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
por: Dinur, Itai, et al.
Publicado: (2021)

The Borsuk number of a graph
por: Cáceres, José, et al.
Publicado: (2026)

Hardness of Finding Kings and Strong Kings
por: Alaoui, Ziad Ismaili, et al.
Publicado: (2025)