High-girth cubic graphs are homomorphic to the Clebsch graph

DOI10.1002/jgt.20580zbMath1231.05093arXivmath/0602580OpenAlexW1991583924WikidataQ105342640 ScholiaQ105342640MaRDI QIDQ3083411

Robert Šámal, Matt DeVos

Publication date: 21 March 2011

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0602580

zbMATH Keywords

circular chromatic numbermax-cutcut-continuous mappings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Tension continuous maps -- their structure and applications

Cites Work

• Universality of \(A\)-mote graphs
• Random cubic graphs are not homomorphic to the cycle of size 7
• Regular graphs with no homomorphisms onto cycles
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• On tension-continuous mappings
• The Fractional Chromatic Number of Graphs of Maximum Degree at Most Three
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Extremal bipartite subgraphs of cubic triangle-free graphs
• On the bipartite density of regular graphs with large girth
• Applications of product colouring
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• A new proof of the independence ratio of triangle-free cubic graphs
• Colorings and homomorphisms of degenerate and bounded degree graphs