Degenerate matchings and edge colorings
From MaRDI portal
Publication:1706114
DOI10.1016/j.dam.2018.01.002zbMath1382.05057arXiv1702.02358OpenAlexW2586268872MaRDI QIDQ1706114
Dieter Rautenbach, Julien Baste
Publication date: 21 March 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.02358
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)
Related Items (12)
Disconnected matchings ⋮ Acyclic Matching in Some Subclasses of Graphs ⋮ Acyclic matchings in graphs of bounded maximum degree ⋮ A lower bound on the acyclic matching number of subcubic graphs ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Acyclic matching in some subclasses of graphs ⋮ Weighted connected matchings ⋮ Revisiting semistrong edge‐coloring of graphs ⋮ Lower bounds on the uniquely restricted matching number ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Disconnected matchings
Cites Work
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- A stronger bound for the strong chromatic index (extended abstract)
- Induced matchings in subcubic graphs without short cycles
- Two greedy consequences for maximum induced matchings
- Feedback vertex set on AT-free graphs
- Matching theory
- Large induced degenerate subgraphs
- NP-completeness of some generalizations of the maximum matching problem
- The strong chromatic index of a cubic graph is at most 10
- Induced matchings
- On the feedback vertex set problem in permutation graphs
- A bound on the strong chromatic index of a graph
- Induced matchings in intersection graphs.
- Uniquely restricted matchings and edge colorings
- Generalized subgraph-restricted matchings in graphs
- On maximum induced matchings in bipartite graphs
- Algorithmic graph theory and perfect graphs
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Maximum induced matchings close to maximum matchings
- Feedback vertex sets in cubic multigraphs
- The graphs with maximum induced matching and maximum matching the same size
- Large induced forests in sparse graphs
- Uniquely Restricted Matchings in Interval Graphs
- Induced matchings in cubic graphs
- Induced Matchings in Subcubic Planar Graphs
- ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS
- Induced Matchings in Subcubic Graphs
- Uniquely restricted matchings
This page was built for publication: Degenerate matchings and edge colorings
