Coloring Graphs with Constraints on Connectivity

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

zbMATH Keywords

local connectivitycoloringBrooks' theoremvertex degreelocal edge-connectivityminimally \(k\)-connected

Mathematics Subject Classification ID

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