Complexity dichotomy for list-5-coloring with a forbidden induced subgraph

DOI10.1137/21M1443352zbMATH Open1496.05051arXiv2105.01787OpenAlexW3198462604MaRDI QIDQ5099103FDOQ5099103

Authors: Sepehr Hajebi, Yanjia Li, Sophie Spirkl 

Publication date: 31 August 2022

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

Abstract: For a positive integer $r$ and graphs $G$ and $H$, we denote by $G+H$ the disjoint union of $G$ and $H$, and by $rH$ the union of $r$ mutually disjoint copies of $H$. Also, we say $G$ is $H$-free if $H$ is not isomorphic to an induced subgraph of $G$. We use $P_t$ to denote the path on $t$ vertices. For a fixed positive integer $k$, the List-$k$-Coloring Problem is to decide, given a graph $G$ and a list $L(v)subseteq1,ldots,k$ of colors assigned to each vertex $v$ of $G$, whether $G$ admits a proper coloring $phi$ with $phi(v)inL(v)$ for every vertex $v$ of $G$, and the $k$-Coloring Problem is the List-$k$-Coloring Problem restricted to instances with $L(v)=1,ldots,k$ for every vertex $v$ of $G$. We prove that for every positive integer $r$, the List-$5$-Coloring Problem restricted to $r{P}_3$-free graphs can be solved in polynomial time. Together with known results, this gives a complete dichotomy for the complexity of the List-$5$-Coloring Problem restricted to $H$-free graphs: For every graph $H$, assuming P$eq$NP, the List-$5$-Coloring Problem restricted to $H$-free graphs can be solved in polynomial time if and only if $H$ is an induced subgraph of either $r{P}_3$ or $P_5+r{P}_1$ for some positive integer $r$. As a hardness counterpart, we also show that the $k$-Coloring Problem restricted to $r{P}_4$-free graphs is NP-complete for all $kgeq5$ and $rgeq2$.

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

Recommendations

• List coloring in the absence of a linear forest
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• List coloring in the absence of a linear forest
• 4-coloring \(H\)-free graphs when \(H\) is small
• Colouring \((P_r + P_s)\)-free graphs

zbMATH Keywords

computational complexitylist coloringinduced subgraphscoloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Reducibility among combinatorial problems
• The complexity of colouring problems on dense graphs
• Title not available (Why is that?)
• The NP-Completeness of Edge-Coloring
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Coloring edges and vertices of graphs without short or long cycles
• Colouring a graph frugally
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Linear and 2-frugal choosability of graphs of small maximum average degree
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Four-coloring \(P_6\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• List coloring in the absence of a linear forest
• Bounding the vertex cover number of a hypergraph
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• List 3-coloring graphs with no induced \(P_6 + rP_3\)

Cited In (9)

• On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
• Colouring \((P_r + P_s)\)-free graphs
• List coloring in the absence of a linear forest
• List coloring in the absence of a linear forest
• List coloring in the absence of two subgraphs
• List coloring in the absence of two subgraphs
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• List-3-coloring ordered graphs with a forbidden induced subgraphs
• Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs

This page was built for publication: Complexity dichotomy for list-5-coloring with a forbidden induced subgraph

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