Fast 3-coloring triangle-free planar graphs

DOI10.1007/S00453-009-9295-2MaRDI QIDQ1957652zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik

Publication date 27 September 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.5116

zbMATH Keywords

ColoringEfficient algorithmGraph algorithmsGrötzsch's theoremTriangle-free planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Algorithms – ESA 2004
• Three-coloring triangle-free planar graphs in linear time
• Three-coloring triangle-free planar graphs in linear time
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• Sub-exponentially many 3-colorings of triangle-free planar graphs

Cites work

• A linear 5-coloring algorithm of planar graphs
• A short list color proof of Grötzsch's theorem
• A sufficient condition for planar graphs to be 3-colorable
• Algorithms – ESA 2004
• Coloring graphs with fixed genus and girth
• Coloring Triangle-Free Graphs on Surfaces
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• scientific article; zbMATH DE number 1256776 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Introduction to algorithms
• Oracles for bounded-length shortest paths in planar graphs
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Some simplified NP-complete graph problems

Cited in

(18)

• 3-dynamic coloring of planar triangulations
• Greedy algorithms for triangle free coloring
• Efficient reassembling of three-regular planar graphs
• Do triangle-free planar graphs have exponentially many 3-colorings?
• Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
• Triangle-free planar graphs with at most \(64^{n^{0.731}}\) 3-colorings
• 3-colorability of pseudo-triangulations
• Vertex-coloring with star-defects
• Orienting dynamic graphs, with applications to maximal matchings and adjacency queries
• Three-coloring triangle-free planar graphs in linear time
• scientific article; zbMATH DE number 1953089 (Why is no real title available?)
• scientific article; zbMATH DE number 1982186 (Why is no real title available?)
• Coloring triangle-free graphs on surfaces
• Three-coloring triangle-free planar graphs in linear time
• On the complexity for constructing a 3-colouring for planar graphs with short facets
• Algorithms – ESA 2004
• scientific article; zbMATH DE number 7053305 (Why is no real title available?)
• Backbone coloring of graphs with galaxy backbones

This page was built for publication: Fast 3-coloring triangle-free planar graphs

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