A Class of Three‐Colorable Triangle‐Free Graphs

DOI10.1002/jgt.21651zbMath1261.05032WikidataQ59902734 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

decomposition; triangle-free graphs; coloring; star cutsets; clique cutsets; induced subdivisions of \(K_{2,3}\)

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Separation Choosability and Dense Bipartite Induced Subgraphs, (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, Excluding clocks, The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs

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