Cycles and new bounds for the chromatic number

DOI10.1016/J.DISC.2022.113255MaRDI QIDQ2111913zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• A Theorem on n-Coloring the Points of a Linear Graph
• Circular colouring and orientation of graphs
• Circumference, chromatic number and online coloring
• Coloring digraphs with forbidden cycles
• Cycle lengths and chromatic number of graphs
• Diconnected Orientations and a Conjecture of Las Vergnas
• Graph coloring in linear time
• Graph theory
• Graph theory and its applications
• Graphs with \(k\) odd cycle lengths
• Nombre chromatique et plus longs chemins d'un graphe
• On approximating the longest path in a graph

Cited in

(7)

• The \(3x+1\) problem: New lower bounds on nontrivial cycle lengths
• Congruence of cycle lengths and chromatic number
• Circumference, chromatic number and online coloring
• Cycle lengths and chromatic number of graphs
• On the connection between the chromatic number of a graph and the number of cycles covering a vertex or an edge
• 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)