List-3-coloring ordered graphs with a forbidden induced subgraphs

MaRDI QIDQ6490276zbMATH OpenFDO

Authors Sepehr Hajebi, Yanjia Li, Sophie Spirkl

Publication date 23 April 2024

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

zbMATH Keywords

algorithmcoloringcomputational complexityinduced subgraphlist-coloringordered graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices

Cites work

• A Ramsey-Type Theorem for Orderings of a Graph
• A survey of -boundedness
• Chromatic number of ordered graphs with forbidden ordered subgraphs
• Coloring edges and vertices of graphs without short or long cycles
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Forbidden paths and cycles in ordered graphs and matrices
• Hard coloring problems in low degree planar bipartite graphs
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• List coloring in the absence of a linear forest
• NP completeness of finding the chromatic index of regular graphs
• On ordered graphs and graph orderings
• On rigid circuit graphs
• On the complexity of some colorful problems parameterized by treewidth
• Pure pairs. VI: Excluding an ordered tree
• Reducibility among combinatorial problems
• The complexity of colouring problems on dense graphs
• The NP-Completeness of Edge-Coloring
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

Cited in

(1)

• A polynomial-time approximation algorithm for complete interval minors

This page was built for publication: List-3-coloring ordered graphs with a forbidden induced subgraphs

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