Three ways to cover a graph

DOI10.1016/j.disc.2015.10.023zbMath1327.05275arXiv1205.1627OpenAlexW2139849594MaRDI QIDQ898135

Torsten Ueckerdt, Kolja Knauer

Publication date: 8 December 2015

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

Full work available at URL: https://arxiv.org/abs/1205.1627

zbMATH Keywords

linear arboricitygraph coveringinterval numbertrack numbercaterpillar arboricitystar arboricity

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (20)

Local boxicity ⋮ An overview of graph covering and partitioning ⋮ Linear layouts of complete graphs ⋮ Local boxicity and maximum degree ⋮ Boolean dimension and local dimension ⋮ Splitting plane graphs to outerplanarity ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ An FPT algorithm for bipartite vertex splitting ⋮ Local and union page numbers ⋮ Local and union boxicity ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ The interval number of a planar graph is at most three ⋮ On the bend-number of planar and outerplanar graphs ⋮ On the planar split thickness of graphs ⋮ On difference graphs and the local dimension of posets ⋮ Nordhaus-gaddum type inequalities for tree covering numbers on unitary cayley graphs of finite rings ⋮ On interval representations of graphs ⋮ On Covering Numbers, Young Diagrams, and the Local Dimension of Posets ⋮ The Local Queue Number of Graphs with Bounded Treewidth ⋮ Fast Diameter Computation within Split Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Biclique covers and partitions
• On the bend-number of planar and outerplanar graphs
• Recognizing graphs with fixed interval number is NP-complete
• The interval number of a planar graph: Three intervals suffice
• Ordered Ramsey theory and track representations of graphs
• Multilayer grid embeddings for VLSI
• On two dual classes of planar graphs
• On the decomposition of graphs into complete bipartite graphs
• On star and caterpillar arboricity
• Covering and packing in graphs. V. Mispacking subcubes in hypercubes
• A short proof of the degree bound for interval number
• Bipartite dimensions and bipartite degrees of graphs
• Star arboricity
• Partitioning graphs of bounded tree-width
• The thickness of graphs: A survey
• Covers of Eulerian graphs
• The star arboricity of graphs
• Star arboricity of graphs
• Graph treewidth and geometric thickness parameters
• Caterpillar arboricity of planar graphs
• Edge-intersection graphs of grid paths: the bend-number
• On double and multiple interval graphs
• Local Clique Covering of Claw-Free Graphs
• The linear arboricity of planar graphs of maximum degree seven is four
• Recognizing d-Interval Graphs and d-Track Interval Graphs
• Factors and factorizations of graphs—a survey
• Some results on linear arboricity
• The NP-Completeness of Edge-Coloring
• Covering and packing in graphs IV: Linear arboricity
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Extremal Values of the Interval Number of a Graph
• Congruent Graphs and the Connectivity of Graphs
• The complexity of finding small triangulations of convex 3-polytopes
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Scheduling Split Intervals
• COVERING AND PACKING IN GRAPHS, I.
• Decomposition of Finite Graphs Into Forests
• Edge intersection graphs of linear 3-uniform hypergraphs
• Linear arboricity and linear \(k\)-arboricity of regular graphs

This page was built for publication: Three ways to cover a graph