Coloring temporal graphs

DOI10.1016/J.JCSS.2021.08.004MaRDI QIDQ2237899zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 28 October 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2021.08.004

zbMATH Keywords

temporal graphslist \(k\)-partite coverst-persistencetemporal coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Sliding window temporal graph coloring
• An introduction to temporal graphs: an algorithmic perspective
• An introduction to temporal graphs: an algorithmic perspective
• Finding colorful paths in temporal graphs
• Edge exploration of temporal graphs

Cites work

• scientific article; zbMATH DE number 3679885 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 1523257 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• k-Components, Clusters and Slicings in Graphs
• A \(c^k n\) 5-approximation algorithm for treewidth
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• A simplified NP-complete satisfiability problem
• All structured programs have small tree width and good register allocation
• An introduction to temporal graphs: an algorithmic perspective
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Bipartite edge partitions and the former Alon-Saks-Seymour conjecture
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Choice Numbers of Graphs: a Probabilistic Approach
• Choosability and fractional chromatic numbers
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
• Exploration of periodically varying graphs
• Graph minors. III. Planar tree-width
• Graph minors. V. Excluding a planar graph
• Graph stories in small area
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs
• Node-and edge-deletion NP-complete problems
• On the Addressing Problem for Loop Switching
• On the size and the approximability of minimum temporally connected subgraphs
• Parameterized algorithms
• Parsimonious flooding in dynamic graphs
• Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data
• Reducibility among combinatorial problems
• Sliding window temporal graph coloring
• The NP-Completeness of Edge-Coloring
• The NP-completeness column: an ongoing guide
• The biparticity of a graph
• The list chromatic index of a bipartite multigraph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations

Cited in

(7)

• Snapshot disjointness in temporal graphs
• An introduction to temporal graphs: an algorithmic perspective
• A new temporal interpretation of cluster editing
• Sliding window temporal graph coloring
• The complexity of computing optimum labelings for temporal connectivity
• Finding colorful paths in temporal graphs
• An introduction to temporal graphs: an algorithmic perspective

This page was built for publication: Coloring temporal graphs

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