3-colouring AT-free graphs in polynomial time

DOI10.1007/s00453-012-9624-8zbMath1257.68075OpenAlexW2024656522MaRDI QIDQ1934316

Juraj Stacho

Publication date: 28 January 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9624-8

zbMATH Keywords

polynomial time algorithmgraph colouringasteroidal tripleinterval graphsstructural decompositionAT-freeco-comparability graphs

Mathematics Subject Classification ID

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

Related Items (7)

Star colouring of bounded degree graphs and regular graphs ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ Solving the clique cover problem on (bull, \(C_4\))-free graphs ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Induced disjoint paths in AT-free graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial optimization with 2-joins
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• Decomposition by clique separators
• Star-cutsets and perfect graphs
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• The ellipsoid method and its consequences in combinatorial optimization
• Some simplified NP-complete graph problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• On stable cutsets in graphs
• On claw-free asteroidal triple-free graphs
• Algorithmic graph theory and perfect graphs
• The NP-Completeness of Edge-Coloring
• Independent Sets in Asteroidal Triple-Free Graphs
• Paths, Trees, and Flowers
• Depth-First Search and Linear Graph Algorithms
• Hidden superconformal symmetry in M-theory

This page was built for publication: 3-colouring AT-free graphs in polynomial time