An algorithm for identifying cycle-plus-triangles graphs

DOI10.1016/J.DAM.2017.04.021MaRDI QIDQ2357769zbMATH OpenOpenAlexFDO

Authors Kristóf Bérczi, Yusuke Kobayashi

Publication date 14 June 2017

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

Full work available at URL https://doi.org/10.1016/j.dam.2017.04.021

zbMATH Keywords

3-colouring\(C_4\)-free 2-matchingcycle-plus-triangles graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An extension of DHH-Erdős conjecture on cycle-plus-triangle graphs
• General parity result and cycle-plus-triangles graphs
• scientific article; zbMATH DE number 524136
• scientific article; zbMATH DE number 970801

Cites work

• A solution to a colouring problem of P. Erdős
• An extension of DHH-Erdős conjecture on cycle-plus-triangle graphs
• Combinatorial Nullstellensatz
• scientific article; zbMATH DE number 25254 (Why is no real title available?)
• scientific article; zbMATH DE number 524136 (Why is no real title available?)
• scientific article; zbMATH DE number 970801 (Why is no real title available?)
• The Hamiltonian property of consecutive-\(d\) digraphs

Cited in

(7)

• Independence number of 2-factor-plus-triangles graphs
• The complexity of finding fair independent sets in cycles
• scientific article; zbMATH DE number 524136 (Why is no real title available?)
• On finding constrained independent sets in cycles
• The cycle discrepancy of three-regular graphs
• An extension of DHH-Erdős conjecture on cycle-plus-triangle graphs
• The complexity of finding fair independent sets in cycles

This page was built for publication: An algorithm for identifying cycle-plus-triangles graphs

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