Coloring Graphs with Constraints on Connectivity
From MaRDI portal
Publication:4978449
DOI10.1002/jgt.22109zbMath1368.05040arXiv1505.01616OpenAlexW790236442MaRDI QIDQ4978449
Dániel Marx, Nick Brettell, Pierre Aboulker, Frédéric Havet, Nicolas Trotignon
Publication date: 10 August 2017
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1505.01616
local connectivitycoloringBrooks' theoremvertex degreelocal edge-connectivityminimally \(k\)-connected
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Vertex degrees (05C07)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs, A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs, Partitioning sparse graphs into an independent set and a forest of bounded degree, A Brooks type theorem for the maximum local edge connectivity, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs, Open Problems on Graph Coloring for Special Graph Classes, A complexity dichotomy for critical values of the b-chromatic number of graphs
Cites Work
- Unnamed Item
- On k-rails in graphs
- Three short proofs in graph theory
- Some simplified NP-complete graph problems
- Which problems have strongly exponential complexity?
- A Brooks type theorem for the maximum local edge connectivity
- The hardness of 3-uniform hypergraph coloring
- Ein Extremalproblem des Zusammenhangs von Graphen
- Grad und lokaler Zusammenhang in endlichen Graphen
- On a conjecture of Bollobas and Erdős
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Depth-First Search and Linear Graph Algorithms