List-3-coloring ordered graphs with a forbidden induced subgraphs
From MaRDI portal
Publication:6490276
Yanjia Li, Sophie Spirkl, Sepehr Hajebi
Publication date: 23 April 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of some colorful problems parameterized by treewidth
- On rigid circuit graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The complexity of colouring problems on dense graphs
- On ordered graphs and graph orderings
- Chromatic number of ordered graphs with forbidden ordered subgraphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- List 3-coloring graphs with no induced \(P_6 + rP_3\)
- List coloring in the absence of a linear forest
- Forbidden paths and cycles in ordered graphs and matrices
- Hard coloring problems in low degree planar bipartite graphs
- The NP-Completeness of Edge-Coloring
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- A Ramsey-Type Theorem for Orderings of a Graph
- NP completeness of finding the chromatic index of regular graphs
- Reducibility among Combinatorial Problems
- Pure Pairs VI: Excluding an Ordered Tree
- A survey of χ‐boundedness
This page was built for publication: List-3-coloring ordered graphs with a forbidden induced subgraphs
