scientific article; zbMATH DE number 6297711

MaRDI QIDQ5417628zbMATH OpenFDO

Authors Erik D. Demaine, Ken-ichi Kawarabayashi, Mohammad T. Hajiaghayi

Publication date 22 May 2014

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Decomposing and clique-coloring (diamond, odd-hole)-free graphs
• Odd decompositions and coverings of graphs
• Note on coloring graphs without odd-\(K_k\)-minors
• Breaking the degeneracy barrier for coloring graphs with no K_t minor
• From edge colorings to graph decompositions -- results and problems
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Coloring graphs having few colorings over path decompositions
• Decompositions of edge-colored complete graphs
• Decomposition of sparse graphs, with application to game coloring number

Cited in

(16)

• Characterising bounded expansion by neighbourhood complexity
• Approximation algorithms via contraction decomposition
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
• Faster approximation schemes and parameterized algorithms on H-minor-free and odd-minor-free graphs
• Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
• Subexponential parameterized algorithms
• Vertex-bipartition method for colouring minor-closed classes of graphs
• Totally odd subdivisions and parity subdivisions: structures and coloring
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Integer programs with bounded subdeterminants and two nonzeros per row
• Clustered colouring of odd-H-minor-free graphs
• Dynamic programming on bipartite tree decompositions
• Dynamic programming on bipartite tree decompositions
• Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs

This page was built for publication:

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