Coloring immersion-free graphs
From MaRDI portal
Publication:326817
DOI10.1016/j.jctb.2016.07.005zbMath1348.05075OpenAlexW2480279973MaRDI QIDQ326817
Ken-ichi Kawarabayashi, Naonori Kakimura
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
Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Edge-disjoint odd cycles in 4-edge-connected graphs
- A minimum degree condition forcing complete graph immersion
- The disjoint paths problem in quadratic time
- The structure of graphs not admitting a fixed immersion
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Topological cliques of random graphs
- Graph minors. XX: Wagner's conjecture
- Some remarks on Hajós' conjecture
- Lower bound of the Hadwiger number of graphs by their average degree
- Immersion in four-edge-connected graphs
- Graph minors XXIII. Nash-Williams' immersion conjecture
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- 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
- Zero knowledge and the chromatic number
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- 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
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- On the conjecture of Hajos
- Graph minors. XIII: The disjoint paths problem
- Über eine Eigenschaft der ebenen Komplexe
- Graph Coloring and the Immersion Order
- Immersing small complete graphs
- An extremal function for contractions of graphs
- Topological cliques in graphs II
- Immersions in Highly Edge Connected Graphs
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- Polynomial bounds for the grid-minor theorem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- 25 pretty graph colouring problems
