scientific article; zbMATH DE number 1076145
A graph is \((m,k)\)-colourable if its vertices can be coloured with \(m\) colours so that each vertex is adjacent to at most \(k\) other vertices of the same colour (so an \((m,0)\)-colouring corresponds to the usual proper colouring). The \(k\)-defective chromatic number \(\chi_k\) is the smallest \(m\) so that a graph can be \((m,k)\)-coloured (so \(\chi_0\) is the usual chromatic number). It is interesting to study chromatic properties of triangle-free graphs. To this end the authors study defective-chromatic properties of triangle-free graphs. In particular, they determine that 9 is the smallest order of a triangle-free graph with 1-defective chromatic number equal to 3, and they find the corresponding graphs. They also give upper and lower bounds on the smallest order of a triangle-free graph with 1-defective chromatic number equal to \(m\).
- On minimal triangle-free graphs with prescribed \(k\)-defective chromatic number
- On defective colorings of triangle-free graphs with prescribed maximum degree
- scientific article; zbMATH DE number 1076149
- On the chromatic number of triangle-free graphs of large minimum degree
- Minimal definable graphs of definable chromatic number at least three
- An open problem on k-defective colourings of triangle-free graphs and their complements
- scientific article; zbMATH DE number 4137784
- Triangle-free graphs with large chromatic numbers
- On minimal triangle-free 6-chromatic graphs
- scientific article; zbMATH DE number 3959463
- Extremal results on defective colorings of graphs
- An open problem on k-defective colourings of triangle-free graphs and their complements
- The Nordhaus-Gaddum problem for the k-defective chromatic number of a P₄-free graph
- Exact Algorithms for a One-defective Vertex Colouring Problem
- scientific article; zbMATH DE number 1076149 (Why is no real title available?)
- On defective colorings of triangle-free graphs with prescribed maximum degree
- On minimal triangle-free graphs with prescribed \(k\)-defective chromatic number
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4359588)
