On a coloring conjecture of Hajós

DOI10.1007/S00373-015-1539-0zbMath1333.05123OpenAlexW2166627576WikidataQ123113649 ScholiaQ123113649MaRDI QIDQ5964996

Xingxing Yu, Yu-Qin Sun

Publication date: 2 March 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-015-1539-0

zbMATH Keywords

planar graphcoloringindependent pathssubdivision of graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Related Items (1)

4‐Separations in Hajós graphs

Cites Work

• Independent paths and \(K_{5}\)-subdivisions
• Disjoint paths in graphs
• 2-linked graphs
• Hajos' graph-coloring conjecture: Variations and counterexamples
• \(3n-5\) edges do force a subdivision of \(K_5\)
• On the conjecture of Hajos
• Reducing Hajós' 4-coloring conjecture to 4-connected graphs
• Applications of Menger's graph theorem
• A Polynomial Solution to the Undirected Two Paths Problem
• Cycles and Connectivity in Graphs
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: On a coloring conjecture of Hajós