Coloring Graphs with Constraints on Connectivity

DOI10.1002/JGT.22109MaRDI QIDQ4978449zbMATH OpenOpenAlexFDO

Authors Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, 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, http://dro.dur.ac.uk/29066/1/29066.pdf

zbMATH Keywords

Brooks' theoremcoloringvertex degreelocal connectivitylocal edge-connectivityminimally \(k\)-connected

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: A graph $G$ has maximal local edge-connectivity $k$ if the maximum number of edge-disjoint paths between every pair of distinct vertices $x$ and $y$ is at most $k$. We prove Brooks-type theorems for $k$-connected graphs with maximal local edge-connectivity $k$, and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph $G$ with maximal local connectivity 3, outputs an optimal colouring for $G$. On the other hand, we prove, for $kge3$, that $k$-colourability is NP-complete when restricted to minimally $k$-connected graphs, and 3-colourability is NP-complete when restricted to $(k-1)$-connected graphs with maximal local connectivity $k$. Finally, we consider a parameterization of $k$-colourability based on the number of vertices of degree at least $k+1$, and prove that, even when $k$ is part of the input, the corresponding parameterized problem is FPT.

Recommendations

• On color-connected graphs
• Constraint propagation in graph coloring
• scientific article; zbMATH DE number 1396705
• Graph coloring satisfying restraints
• scientific article; zbMATH DE number 446487
• Graph coloring with cardinality constraints on the neighborhoods
• Properly colored connectivity of graphs
• Feasible Graphs and Colorings
• The coloring of graphs
• Sur le coloriage des graphs

Cites work

• A Brooks type theorem for the maximum local edge connectivity
• Depth-First Search and Linear Graph Algorithms
• Ein Extremalproblem des Zusammenhangs von Graphen
• Grad und lokaler Zusammenhang in endlichen Graphen
• Lower bounds based on the exponential time hypothesis
• On a conjecture of Bollobas and Erdős
• On k-rails in graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• Some simplified NP-complete graph problems
• The hardness of 3-uniform hypergraph coloring
• Three short proofs in graph theory
• Which problems have strongly exponential complexity?

Cited in

(16)

• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Coloring k-colorable graphs using smaller palettes
• A Brooks type theorem for the maximum local edge connectivity
• Properties of uniformly \(3\)-connected graphs
• A complexity dichotomy for critical values of the b-chromatic number of graphs
• Open problems on graph coloring for special graph classes
• On the exact \& approximate complexity of the strongly connected Steiner subgraph problem on two terminals with demands
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Brooks-type colourings of digraphs in linear time
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• scientific article; zbMATH DE number 3885934 (Why is no real title available?)
• Coloring hypergraphs of low connectivity
• Hard-to-color graphs for connected sequential colorings
• A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs
• Partitioning sparse graphs into an independent set and a forest of bounded degree

This page was built for publication: Coloring Graphs with Constraints on Connectivity

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