Coloring immersion-free graphs

DOI10.1016/J.JCTB.2016.07.005zbMATH Open1348.05075OpenAlexW2480279973MaRDI QIDQ326817FDOQ326817

Authors: Naonori Kakimura, Ken-ichi Kawarabayashi 

Publication date: 12 October 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2016.07.005

Recommendations

• Immersion and clustered coloring
• List-coloring graphs without subdivisions and without immersions
• Constructing graphs with no immersion of large complete graphs
• Improper colourings inspired by Hadwiger's conjecture
• Graph coloring and the immersion order

zbMATH Keywords

coloringfixed-parameter algorithmimmersion

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Cites Work

• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Title not available (Why is that?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph minors. XX: Wagner's conjecture
• A bound on the chromatic number of a graph
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Graph minors. XIII: The disjoint paths problem
• Über eine Eigenschaft der ebenen Komplexe
• An extremal function for contractions of graphs
• Title not available (Why is that?)
• Lower bound of the Hadwiger number of graphs by their average degree
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Highly connected sets and the excluded grid theorem
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Quickly excluding a planar graph
• The four-colour theorem
• Edge-disjoint odd cycles in 4-edge-connected graphs
• Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid
• The disjoint paths problem in quadratic time
• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• Title not available (Why is that?)
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Topological cliques in graphs II
• Polynomial bounds for the grid-minor theorem
• 25 pretty graph colouring problems
• Title not available (Why is that?)
• Zero knowledge and the chromatic number
• The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
• On the conjecture of Hajos
• Graph coloring and the immersion order
• Immersing small complete graphs
• Title not available (Why is that?)
• A minimum degree condition forcing complete graph immersion
• The structure of graphs not admitting a fixed immersion
• Immersions in highly edge connected graphs
• An improved algorithm for finding tree decompositions of small width
• Topological cliques of random graphs
• Some remarks on Hajós' conjecture
• Immersion in four-edge-connected graphs
• Graph minors XXIII. Nash-Williams' immersion conjecture

Cited In (5)

• Immersion and clustered coloring
• Packing and covering immersion models of planar subcubic graphs
• Graph coloring and the immersion order
• List-coloring graphs without subdivisions and without immersions
• Induced immersions

This page was built for publication: Coloring immersion-free graphs

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