An algorithm for identifying cycle-plus-triangles graphs

DOI10.1016/j.dam.2017.04.021zbMath1365.05272OpenAlexW2615239789MaRDI QIDQ2357769

Yusuke Kobayashi, Kristóf Bérczi

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

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

Related Items (2)

On finding constrained independent sets in cycles ⋮ The complexity of finding fair independent sets in cycles

Cites Work

• An extension of DHH-Erdős conjecture on cycle-plus-triangle graphs
• A solution to a colouring problem of P. Erdős
• The Hamiltonian property of consecutive-\(d\) digraphs
• Combinatorial Nullstellensatz
• Unnamed Item
• Unnamed Item
• Unnamed Item

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