A class of three-colorable triangle-free graphs
From MaRDI portal
Recommendations
- Triangle-free graphs that do not contain an induced subdivision of K₄ are 3-colorable
- Triangle-free 2P₃-free graphs are 4-colorable
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
- 3-colourability and forbidden subgraphs
Cites work
- Alpha-balanced graphs and matrices and GF(3)-representability of matroids
- Decomposition by clique separators
- Graph Theory and Probability
- scientific article; zbMATH DE number 1496606 (Why is no real title available?)
- Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- The three-in-a-tree problem
- Universally signable graphs
- Vertex colouring and forbidden subgraphs -- a survey
Cited in
(25)- Coloring triangle-free graphs with fixed size
- Triangle-free graphs and forbidden subgraphs
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- On vertex coloring without monochromatic triangles
- Three colorability characterized by shrinking of locally connected subgraphs into triangles
- Greedy algorithms for triangle free coloring
- Triangle-free 2P₃-free graphs are 4-colorable
- The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
- Tiling tripartite graphs with 3-colorable graphs
- Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable
- Triangle-free graphs without forbidden subgraphs
- Excluding clocks
- On the chromatic number of path graph P₃(G)
- Color class sizes of triangle-free graphs
- Coloring triangle-free graphs on surfaces
- scientific article; zbMATH DE number 6939351 (Why is no real title available?)
- Separation choosability and dense bipartite induced subgraphs
- Triangle-free graphs that do not contain an induced subdivision of K₄ are 3-colorable
- A characterization of small 3-colorable graphs
- On the maximal triangle-free edge-chromatic graphs in three colors
- Triangle-free Uniquely 3-Edge Colorable Cubic 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
- (Even hole, triangle)-free graphs revisited
- A constructive characterization of 3-connected triangle-free graphs
This page was built for publication: A class of three-colorable triangle-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4916101)
