Cycles and new bounds for the chromatic number

DOI10.1016/J.DISC.2022.113255zbMATH Open1506.05062OpenAlexW4309340876MaRDI QIDQ2111913FDOQ2111913

Authors: Narda Cordero-Michel, Hortensia Galeana-Sánchez, Ilan A. Goldfeder 

Publication date: 17 January 2023

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

Full work available at URL: https://doi.org/10.1016/j.disc.2022.113255

Recommendations

• New Bounds for the Dichromatic Number of a Digraph
• Colourings with Bounded Monochromatic Components in Graphs of Given Circumference
• Circumference, chromatic number and online coloring
• Cycles in triangle-free graphs of large chromatic number
• Cycle lengths and chromatic number of graphs

zbMATH Keywords

chromatic numberproper coloringDFS algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cites Work

• Graph theory
• Coloring digraphs with forbidden cycles
• On approximating the longest path in a graph
• Nombre chromatique et plus longs chemins d'un graphe
• Circular colouring and orientation of graphs
• Title not available (Why is that?)
• Graphs with \(k\) odd cycle lengths
• Cycle lengths and chromatic number of graphs
• A Theorem on n-Coloring the Points of a Linear Graph
• Graph coloring in linear time
• Diconnected Orientations and a Conjecture of Las Vergnas
• Circumference, chromatic number and online coloring
• Graph Theory and Its Applications

Cited In (5)

• The \(3x+1\) problem: New lower bounds on nontrivial cycle lengths
• Congruence of cycle lengths and chromatic number
• Cycle lengths and chromatic number of graphs
• On the number of bounding cycles for nonlinear arrangements
• A quick way to verify if a graph is 3-colorable

This page was built for publication: Cycles and new bounds for the chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111913)