Coloring immersion-free graphs

DOI10.1016/J.JCTB.2016.07.005MaRDI QIDQ326817zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)