Smallest \(C_{2 \ell + 1}\)-critical graphs of odd-girth \(2 k + 1\)

DOI10.1016/j.dam.2021.08.040zbMath1494.05043arXiv1610.03685OpenAlexW4210756155WikidataQ113877219 ScholiaQ113877219MaRDI QIDQ2161276

Reza Naserasr, Florent Foucaud, Laurent Beaudou

Publication date: 4 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

homomorphismsgraph colouringodd-cycles

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Uses Software

• MathOverflow

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ore's conjecture on color-critical graphs is almost true
• Smallest \(C_{2l+1}\)-critical graphs of odd-girth \(2k+1\)
• Note on robust critical graphs with large odd girth
• Graph homomorphisms into the five-cycle
• On the chromatic number of cube-like graphs
• Density of 5/2-critical graphs
• 4-chromatic graphs with large odd girth
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Density of \(C_{-4}\)-critical signed graphs
• On the density of \(C_7\)-critical graphs
• Small odd cycles in 4-chromatic graphs
• Fractional chromatic numbers of cones over graphs
• Homomorphisms of graphs into odd cycles
• Graph Theory and Probability
• Short odd cycles in 4-chromatic graphs
• The width of quadrangulations of the projective plane
• On graphs with strongly independent color-classes
• 4-chromatic projective graphs
• Bounds for the smallest $k$-chromatic graphs of given girth
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Sur le coloriage des graphs
• Circular chromatic number: A survey

This page was built for publication: Smallest \(C_{2 \ell + 1}\)-critical graphs of odd-girth \(2 k + 1\)