Orientable burning number of graphs

DOI10.1016/J.DAM.2025.02.004MaRDI QIDQ7011768zbMATH OpenFDO

Authors Julien Courtiel, Paul Dorbec, Tatsuya Gima, Yota Otachi

Publication date 18 March 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.02.004

zbMATH Keywords

burning numberfixed-parameter algorithmgraph orientation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Cites work

• A greedy partition lemma for directed domination
• A survey of graph burning
• Approximation algorithms and lower bounds for graph burning
• APX-hardness and approximation for the \(k\)-burning number problem
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Burn and win
• Burning a graph as a model of social contagion
• Burning a graph is hard
• Burning number of caterpillars
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Directed domination in oriented graphs
• Distances in orientations of graphs
• Domination and fractional domination in digraphs
• Easy problems for tree-decomposable graphs
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Fixed-parameter algorithms for cluster vertex deletion
• Fundamentals of parameterized complexity
• Geometric algorithms and combinatorial optimization
• Graph burning and non-uniform \(k\)-centers for small treewidth
• Graphen und Matrices.
• How to Burn a Graph
• scientific article; zbMATH DE number 1161297 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Minimizing and maximizing the diameter in orientations of graphs
• Nombre chromatique et plus longs chemins d'un graphe
• Normal hypergraphs and the perfect graph conjecture
• On a division property of consecutive integers
• On a Problem in Graph Theory
• On some graph classes related to perfect graphs: a survey
• Parameterized algorithms
• Parameterized algorithms for Graph Burning problem
• Parameterized complexity of graph burning
• Parametrized complexity theory.
• The burning number conjecture holds asymptotically
• The burning number of directed graphs: bounds and computational complexity
• The complexity of two graph orientation problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. VIII: Orientations
• The Rectilinear Steiner Tree Problem is NP-Complete
• The trouble with the second quantifier
• Transmitting in the n-dimensional cube
• Zur algebraischen Begründung der Graphentheorie. I
• Über kombinatorische Eigenschaften von Matrizen.

Cited in

(1)

• Burning path-like and clique-like graphs

This page was built for publication: Orientable burning number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7011768)