Structure and Coloring of Graphs with Only Small Odd Cycles

DOI10.1137/S0895480197323883MaRDI QIDQ3394987zbMATH OpenOpenAlexFDO

Authors Susan S. Wang

Publication date 20 August 2009

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

Full work available at URL https://doi.org/10.1137/s0895480197323883

zbMATH Keywords

algorithmschromatic numbergraph coloringodd cyclesstructural characterization of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Recommendations

• Odd properly colored cycles in edge-colored graphs
• Colourings of graphs with two consecutive odd cycle lengths
• Edge-disjoint odd cycles in graphs with small chromatic numbers
• On graphs with a large chromatic number that contain no small odd cycles
• Small odd cycles in 4-chromatic graphs
• Coloring graphs with two odd cycle lengths
• Vertex colorings of graphs without short odd cycles
• Odd graph and its applications to the strong edge coloring
• Odd coloring of sparse graphs and planar graphs
• Remarks on odd colorings of graphs

Cited in

(3)

• Coloring graphs with two odd cycle lengths
• Subdivisions of four blocks cycles in digraphs with large chromatic number
• Nowhere-zero 3-flows of graphs with prescribed sizes of odd edge cuts

This page was built for publication: Structure and Coloring of Graphs with Only Small Odd Cycles

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