Coloring graphs with two odd cycle lengths

DOI10.1137/15M1053773MaRDI QIDQ4602857zbMATH OpenOpenAlexFDO

Authors Jie Ma, Bo Ning

Publication date 7 February 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

3-colorabilitychromatic numbercritical graphodd cycle length

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45)

Abstract: In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let $G$ be a graph and $L(G)$ be the set of all odd cycle lengths of $G$. We prove that: (1) If $L(G)=3,3+2l$, where $lgeq2$, then $chi(G)=max3,omega(G)$; (2) If $L(G)=k,k+2l$, where $kgeq5$ and $lgeq1$, then $chi(G)=3$. These, together with the case $L(G)=3,5$ solved in cite{W}, give a complete solution to the general problem addressed in cite{W,CS,KRS}. Our results also improve a classical theorem of Gy'{a}rf'{a}s which asserts that $chi(G)le2|L(G)|+2$ for any graph $G$.

Recommendations

• Graphs with odd cycle lengths 5 and 7 are 3-colorable
• Colourings of graphs with two consecutive odd cycle lengths
• Graphs with \(k\) odd cycle lengths
• scientific article; zbMATH DE number 3904622
• Cycle lengths and chromatic number of graphs

Cites work

• Colourings of graphs with two consecutive odd cycle lengths
• Cycle lengths and minimum degree of graphs
• Cycles in triangle-free graphs of large chromatic number
• Graph theory
• Graphs having circuits with at least two chords
• Graphs with \(k\) odd cycle lengths
• Graphs with odd cycle lengths 5 and 7 are 3-colorable
• scientific article; zbMATH DE number 4164941 (Why is no real title available?)
• scientific article; zbMATH DE number 49078 (Why is no real title available?)
• scientific article; zbMATH DE number 554066 (Why is no real title available?)
• scientific article; zbMATH DE number 1117463 (Why is no real title available?)
• Non-separating induced cycles in graphs
• Structure and Coloring of Graphs with Only Small Odd Cycles
• The structure of k-chromatic graphs

Cited in

(14)

• List coloring of graphs having cycles of length divisible by a given number
• Colourings of graphs with two consecutive odd cycle lengths
• Graphs with \(k\) odd cycle lengths
• Circumference, chromatic number and online coloring
• Small odd cycles in 4-chromatic graphs
• Cycle length parities and the chromatic number
• Graphs with odd cycle lengths 5 and 7 are 3-colorable
• Structure and Coloring of Graphs with Only Small Odd Cycles
• A bound on the chromatic number using the longest odd cycle length
• scientific article; zbMATH DE number 1305541 (Why is no real title available?)
• Excluding cycles with a fixed number of chords
• A strengthening on odd cycles in graphs of given chromatic number
• Congruence of cycle lengths and chromatic number
• The chromatic number of a graph with two odd holes and an odd girth

This page was built for publication: Coloring graphs with two odd cycle lengths

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