A Class of Three‐Colorable Triangle‐Free Graphs

DOI10.1002/jgt.21651zbMath1261.05032OpenAlexW1843729564WikidataQ59902734 ScholiaQ59902734MaRDI QIDQ4916101

Kristina Vušković, Marko Radovanović

Publication date: 19 April 2013

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/79075/7/t3pcfree_with_coversheet.pdf

zbMATH Keywords

decompositiontriangle-free graphscoloringstar cutsetsclique cutsetsinduced subdivisions of \(K_{2,3}\)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Excluding clocks ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Separation Choosability and Dense Bipartite Induced Subgraphs

Cites Work

• Unnamed Item
• The three-in-a-tree problem
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Decomposition by clique separators
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Universally signable graphs
• Vertex colouring and forbidden subgraphs -- a survey
• Graph Theory and Probability

This page was built for publication: A Class of Three‐Colorable Triangle‐Free Graphs