High-girth graphs avoiding a minor are nearly bipartite

DOI10.1006/jctb.2000.2009zbMath1028.05034OpenAlexW2039256426MaRDI QIDQ1850553

Anna Galluccio, Luis A. Goddyn, Pavol Hell

Publication date: 10 December 2002

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

Full work available at URL: https://doi.org/10.1006/jctb.2000.2009

zbMATH Keywords

circular chromatic numberhomomorphismgirthgenusforbidden minors

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Related Items (19)

On the odd girth and the circular chromatic number of generalized Petersen graphs ⋮ A revival of the girth conjecture ⋮ A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems ⋮ The circular chromatic index of graphs of high girth ⋮ Graphs with bounded tree-width and large odd-girth are almost bipartite ⋮ Fractional coloring planar graphs under Steinberg-type conditions ⋮ Nearly nowhere-zero \(r\)-flow graphs ⋮ Homomorphisms from sparse graphs with large girth. ⋮ Nowhere-zero 3-flows and modulo \(k\)-orientations ⋮ Circular consecutive choosability of k-choosable graphs ⋮ On circle graphs with girth at least five ⋮ Box representations of embedded graphs ⋮ A Complexity Dichotomy for the Coloring of Sparse Graphs ⋮ Islands in Graphs on Surfaces ⋮ Circular chromatic number of signed graphs ⋮ Circular choosability ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Circular flows of nearly Eulerian graphs and vertex-splitting ⋮ Distributed algorithms for fractional coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bound of the Hadwiger number of graphs by their average degree
• Nowhere-zero 6-flows
• Chromatic number and girth
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Homomorphisms of graphs into odd cycles
• An extremal function for contractions of graphs
• Graph minors. II. Algorithmic aspects of tree-width
• On (k,d)-colorings and fractional nowhere-zero flows
• 4-chromatic projective graphs
• A 4-Color Theorem for Toroidal Graphs
• Circular chromatic number: A survey

This page was built for publication: High-girth graphs avoiding a minor are nearly bipartite